呼伦贝尔网站建设公司,店面效果图制作软件,蘑菇街的网站建设,福建祥盛建设有限公司网站题目描述
有一个仅由数字 00 与 11 组成的 #xfffd;#xfffd;nn 格迷宫。若你位于一格 00 上#xff0c;那么你可以移动到相邻 44 格中的某一格 11 上#xff0c;同样若你位于一格 11 上#xff0c;那么你可以移动到相邻 44 格中的某一格 00 上。
你的任务是#…题目描述
有一个仅由数字 00 与 11 组成的 ×n×n 格迷宫。若你位于一格 00 上那么你可以移动到相邻 44 格中的某一格 11 上同样若你位于一格 11 上那么你可以移动到相邻 44 格中的某一格 00 上。
你的任务是对于给定的迷宫询问从某一格开始能移动到多少个格子包含自身。
输入格式
第一行为两个正整数 ,n,m。
下面 n 行每行 n 个字符字符只可能是 00 或者 11字符之间没有空格。
接下来 m 行每行两个用空格分隔的正整数 ,i,j对应了迷宫中第 i 行第 j 列的一个格子询问从这一格开始能移动到多少格。
输出格式
m 行对于每个询问输出相应答案。
输入输出样例
输入 #1复制
2 2
01
10
1 1
2 2输出 #1复制
4
4说明/提示
对于样例所有格子互相可达。
对于 20%20% 的数据≤10n≤10对于 40%40% 的数据≤50n≤50对于 50%50% 的数据≤5m≤5对于 60%60% 的数据,≤100n,m≤100对于 100%100% 的数据1≤≤10001≤n≤10001≤≤1000001≤m≤100000。
想法
这题也是dfs求连通块不过细胞那题是求连通块的个数这题是求一个连通块中有多少个块。代码如下。
代码
#includebits/stdc.h using namespace std; int ans; char mg[1010][1010];//迷宫 int n,m; int st[1010][1010];//状态数组 int dx[]{0,0,1,-1};//四个方向 int dy[]{1,-1,0,0}; void dfs(int x,int y){ for(int i0;i4;i){ int xxdx[i]x; int yydy[i]y; if(xxn||xx1||yyn||yy1) continue;//超范围 if(st[xx][yy]1) continue;//走过了 if(mg[xx][yy]mg[x][y]) continue;//走不了 st[xx][yy]1; ans; dfs(xx,yy); } } int main(){ cinnm; for(int i1;in;i){ for(int j1;jn;j){ cinmg[i][j]; } } int a,b; while(m--){ memset(st,0,sizeof(st)); ans1; cinab; st[a][b]1; dfs(a,b); coutansendl; } }
然而事情没有这么简单这题这么写会超时因为查询的次数太多了查过的点还要重新计算答案而且属于同一个联通块的点的答案还是一样的这样就可以用到记忆化搜索。虽然这个也不是我推的了解一下咯。它这记忆化也是蛮巧妙的吧用一个二维数组存坐标一个二维数组存答案就是直接将整个迷宫的答案都搜一遍并存起来后面直接查询。而且它搜联通块和搜答案是一起的就是记忆化和搜答案是一起的。
代码
#includebits/stdc.h using namespace std; int n,m; int ans1; int Ans[1010][1010]; int zb[1000010][2];//坐标 int st[1010][1010]; char mg[1010][1010]; int dx[]{0,0,1,-1}; int dy[]{1,-1,0,0}; void dfs(int x,int y){ for(int i0;i4;i){ int xxdx[i]x; int yydy[i]y; if(xxn||xx1||yyn||yy1) continue;//超范围 if(mg[x][y]mg[xx][yy]) continue;//走不到 if(st[xx][yy]1) continue;//走过了 ans; st[xx][yy]1; zb[ans][0]xx;//存坐标 zb[ans][1]yy; dfs(xx,yy); } } int main(){ cinnm; for(int i1;in;i){ for(int j1;jn;j) cinmg[i][j]; } for(int i1;in;i){ for(int j1;jn;j){ if(st[i][j]0){//搜连通块 st[i][j]1; ans1; zb[1][0]i; zb[1][1]j; dfs(i,j); for(int k1;kans;k){//存答案 Ans[zb[k][0]][zb[k][1]]ans; } } } } int a,b; while(m--){ cinab; coutAns[a][b]endl; } } 注意
存图的时候看看给的图有没有连起来这样判断数组用int还是char。
