首页 > 代码库 > 洛谷——P1141 01迷宫
洛谷——P1141 01迷宫
https://www.luogu.org/problem/show?pid=1141
题目描述
有一个仅由数字0与1组成的n×n格迷宫。若你位于一格0上，那么你可以移动到相邻4格中的某一格1上，同样若你位于一格1上，那么你可以移动到相邻4格中的某一格0上。
你的任务是：对于给定的迷宫，询问从某一格开始能移动到多少个格子（包含自身）。
输入输出格式
输入格式：
输入的第1行为两个正整数n，m。
下面n行，每行n个字符，字符只可能是0或者1，字符之间没有空格。
接下来m行，每行2个用空格分隔的正整数i,j，对应了迷宫中第i行第j列的一个格子，询问从这一格开始能移动到多少格。
输出格式：
输出包括m行，对于每个询问输出相应答案。
输入输出样例
输入样例#1：
2 201101 12 2
输出样例#1：
44
说明
所有格子互相可达。
对于20%的数据，n≤10；
对于40%的数据，n≤50；
对于50%的数据，m≤5；
对于60%的数据，n≤100，m≤100；
对于100%的数据，n≤1000，m≤100000。
搜过的记一下。。
1 #include <algorithm> 2 #include <iostream> 3 #include <cstring> 4 #include <cstdio> 5 #include <queue> 6 7 using namespace std; 8 9 const int N(1000+15); 10 int n,m,x,y,map[N][N];11 char ch;12 struct Node13 {14 int x,y;15 }node;16 17 int cnt[N*N],vis[N][N],col[N*N],sumcol;18 int fx[4]={0,1,0,-1};19 int fy[4]={1,0,-1,0};20 void BFS(Node s)21 {22 queue<Node>que;23 que.push(s);24 vis[s.x][s.y]=sumcol;25 cnt[sumcol]++;26 for(;!que.empty();)27 {28 Node a,fro=que.front();29 que.pop();30 for(int i=0;i<4;i++)31 {32 int xx=fro.x+fx[i],yy=fro.y+fy[i];33 if(vis[xx][yy]||xx<1||yy<1||xx>n||yy>n) continue;34 if(abs(map[xx][yy]-map[fro.x][fro.y])!=1) continue;35 cnt[sumcol]++; a.x=xx,a.y=yy;36 vis[a.x][a.y]=sumcol; que.push(a);37 }38 }39 }40 41 inline void read(int &x)42 {43 x=0;ch=getchar();44 for(;ch<‘0‘||ch>‘9‘;) ch=getchar();45 for(;ch>=‘0‘&&ch<=‘9‘;ch=getchar())46 x=ch-‘0‘+x*10;47 }48 49 int main()50 {51 read(n); read(m);52 for(int i=1;i<=n;i++)53 for(int j=1;j<=n;j++)54 cin>>ch,map[i][j]=ch-‘0‘;55 for(int i=1;i<=m;i++)56 {57 read(node.x); read(node.y);58 sumcol=i;59 if(!vis[node.x][node.y]) BFS(node);60 printf("%d\n",cnt[vis[node.x][node.y]]);61 }62 return 0;63 }
洛谷——P1141 01迷宫
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。