题目大意:n*n的网格,每个网格是一个房间
都关着灯,只有(1,1)开着灯,且(x,y)有着(z,k)房间灯的开关。
问从(1,1)开始走最多点开几盏灯。
题解:搜索+骗分。
劳资的骗分天下无敌,劳资的骗分世界第一
代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#define N 102
using namespace std; int n,m,ans=,js; int vis[N][N],b[N][N],ok[N][N]; int mx[]={,,-,},
my[]={,,,-}; struct node{
int x,y;
}; struct T{
int x,y;
}; queue<T>q; vector<node>a[N][N]; void bfs(){
T c;c.x=;c.y=;q.push(c);
vis[][]=true;b[][]=true;
while(!q.empty()){
T now=q.front();q.pop();js++;
if(js==n*n*)return; //遍历了这么多遍应该灯应该都开了吧。
int xx=now.x,yy=now.y;
for(int i=;i<a[xx][yy].size();i++){
node g=a[xx][yy][i];
if(b[g.x][g.y]==)ans++;
b[g.x][g.y]=true;
}
for(int i=;i<;i++){
int nx=xx+mx[i],ny=yy+my[i];
if(nx<||nx>n||ny<||ny>n||vis[nx][ny]||b[nx][ny]==) continue;
vis[nx][ny]=true;
T tmp;tmp.x=nx;tmp.y=ny;
q.push(tmp);
}
q.push(now);
}
} int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++){
int x,y,nx,ny;
scanf("%d%d%d%d",&x,&y,&nx,&ny);
node t;t.x=nx;t.y=ny;
a[x][y].push_back(t);
}
bfs();
printf("%d\n",ans);
return ;
}
AC
骗分归骗分正解还是要学的
每点开一盏灯,看这盏灯的上下左右是否被点开灯了
有被点开的就开始搜这个点。
洛谷 P2828 Switching on the Lights(开关灯)的更多相关文章
-
洛谷P2828 Switching on the Lights(开关灯)
P2828 Switching on the Lights(开关灯) 题目背景 来源:usaco-2015-dec Farm John 最近新建了一批巨大的牛棚.这些牛棚构成了一个N*N的矩形网络.( ...
-
搜索【洛谷P2845】 [USACO15DEC]Switching on the Lights 开关灯
P2845 [USACO15DEC]Switching on the Lights 开关灯 题目背景 来源:usaco-2015-dec Farm John 最近新建了一批巨大的牛棚.这些牛棚构成了一 ...
-
Luogu P2845 [USACO15DEC]Switching on the Lights 开关灯(bfs)
P2845 [USACO15DEC]Switching on the Lights 开关灯 题意 题目背景 来源:usaco-2015-dec \(Farm\ John\)最近新建了一批巨大的牛棚.这 ...
-
P2845 [USACO15DEC]Switching on the Lights 开关灯
题目背景 来源:usaco-2015-dec Farm John 最近新建了一批巨大的牛棚.这些牛棚构成了一个N*N的矩形网络.(1<n<100) 然而bessie十分怕黑,他想计算可以把 ...
-
luogu P2828 Switching on the Lights(开关灯)
题目背景 来源:usaco-2015-dec Farm John 最近新建了一批巨大的牛棚.这些牛棚构成了一个N*N的矩形网络.(1<n<100) 然而bessie十分怕黑,他想计算可以把 ...
-
「Luogu P2845 [USACO15DEC]Switching on the Lights 开关灯」
USACO的又一道搜索题 前置芝士 BFS(DFS)遍历:用来搜索.(因为BFS好写,本文以BFS为准还不是因为作者懒) 链式前向星,本题的数据比较水,所以邻接表也可以写,但是链式前向星它不香吗. 具 ...
-
洛谷P2845-Switching on the Lights 开关灯
Problem 洛谷P2845-Switching on the Lights 开关灯 Accept: 154 Submit: 499Time Limit: 1000 mSec Memor ...
-
COCI2017-2018#3 Dojave || 洛谷P4443
题目传送门............................................................................................... ...
-
洛谷1640 bzoj1854游戏 匈牙利就是又短又快
bzoj炸了,靠离线版题目做了两道(过过样例什么的还是轻松的)但是交不了,正巧洛谷有个"大牛分站",就转回洛谷做题了 水题先行,一道傻逼匈牙利 其实本来的思路是搜索然后发现写出来类 ...
随机推荐
-
Jquery 搭配 css 使用,简单有效
前几篇博客中讲了Jquery的基础和点击实际,下面来说一下和css搭配着来怎么做 还是和往常一样,举个例子 好几个方块,然后设置颜色 <!DOCTYPE html PUBLIC "-/ ...
-
freemarker 分页取值
<#if pagination??&&pagination.list??> <#list pagination.list as video> <td al ...
-
内核编译选配(VMware篇)
出现这个错误的原因是相应的驱动程序没有编译进内核,所以在内核启动时,不认识分区. 一.磁盘驱动没编译进内核 VMware5.5.3 的磁盘有两种,一种是IDE的,一种是SCSI的:VMware 你在新 ...
-
SpringMVC -- 梗概--壹
1.springMVC:MVC开源框架 2.springMVC开发流程: 2.1 导包: 2.2 配置前端控制器(核心) DispatcherServlet <servlet> <s ...
-
Oracle列操作引起的全表扫描
首先是一种比较明显的情况: select * from table where column + 1 = 2 这里对column进行了列操作,加1以后,与column索引里的内容对不上,导致colum ...
-
hdoj 2044一只小蜜蜂...【斐波那契变形】
一只小蜜蜂... Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Su ...
-
oldboy第五天学习
一.生成器 列表生成器 >>> a [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] >>> b = [] >>> for i in ...
-
c#中WebBrowser控件的使用方法
首先先来简单介绍一下webbrowser控件,这个控件是可以实现在form窗体中添加网页内容的.如图,我在form中加入了百度api,(百度地图api调用博客里有讲) 使用这个控件其实很简单 (1)第 ...
-
python del关键字的用法
del Keyword 注意del是python关键字,就像def.and.or一样.它不是字典.列表的方法,但是可以用来删除字典.列表的元素.比如: del list_item[4] del dic ...
-
Confluence 6 更新目录
当编辑目录时候的限制 你不能对你用户属于的目录进行编辑,禁用或者删除.这个能够预防管理员通过修改目录的时候讲自己属于的管理员权限从系统管理员组中删除. 这个限制对所有的用户目录类型适用.例如: 如果当 ...