解题报告 P1141 【01迷宫】广度优先搜索

迷宫这个模型各位OIer见得可多了，一般是搜索类题目，同样地，这道题是一道~~**巨坑**~~浅显的广搜题 我们直接看判断条件：在当前点可以走到相邻的不同数字的点上去 这个题有多个询问，并且$m\le100,000$，所以每次做一遍BFS肯定不现实（事实证明这样还是有$70$分的），所以要用到记忆化搜索，这样才能减少时间开销。 记忆化搜索思想：已经搜到的联通块不必再搜，将处于相同联通块的格子用并查集并起来，即在之后的搜索中，一旦搜索到与当前状态的格子处于相同联通块的格子，则直接跳过，则一个联通块只会搜到一次。那么当一个点更新完时，与它相连的联通块的值（可以到达的点）一定和它一样，用vis数组存下来，这样可以用vis数组代替bool数组used（我的最初程序也用到了used，后来发现不需要，不知道bool数组调用时会不会稍微快一点），因此在之后vis不为0的点就不需要入队了。 #### 说到used数组，有一个重要的点希望大家不要被坑了 就是不要在每次的bfs里都对used数组重置一遍，第一很费时间，第二，完全没有必要，第三，想打裸的BFS（$70$分）用used是需要每次重置的，因为每次相当于重新做了一遍，没有用到记忆化 **另一个注意事项**：在相邻格子遍历时，千万不要越界，所以大家看到我的判断条件比较长**~~（其实一个for循环解决一切）~~**，多一个条件保险一些。 **再一个注意事项**，这个题的输入格式是字符形式，所以要考虑行末有没有'\n'（用cin当我没说，其实也可以过）要特意读入一下 剩下的就是考广搜的基本功啦 ------------ # Code: ```cpp #include<cstring> #include<cstdio> #include<queue> using namespace std; struct point { int x,y; }t[1000005]; queue<point> q; int a[1001][1001],vis[1001][1001],s[1000005]; int n,m,u[1001][1001]; int Find(int x) { if(s[x]==x) return s[x]; return s[x]=Find(s[x]); } void Union(int x,int y) { s[Find(y)]=s[Find(x)]; return ; } void turn(int x)//预处理坐标转换（用空间换时间） { for(int i=1;i<=x;i++) for(int j=1;j<=x;j++) u[i][j]=(i-1)*n+j; return; } int bfs(int x,int y) { int ans=0,k=0; point p; p.x=x; p.y=y; q.push(p); while(!q.empty()) { p=q.front(); q.pop(); t[++k].x=p.x; t[k].y=p.y; if(vis[p.x][p.y]) { ans+=vis[p.x][p.y]; continue; } ans++; if(!vis[p.x-1][p.y]&&p.x>1&&a[p.x-1][p.y]!=a[p.x][p.y]) if(Find(u[p.x-1][p.y])!=Find(u[p.x][p.y])) { p.x--; q.push(p); p.x++; Union(u[p.x-1][p.y],u[p.x][p.y]); } if(!vis[p.x+1][p.y]&&p.x<n&&a[p.x+1][p.y]!=a[p.x][p.y]) if(Find(u[p.x+1][p.y])!=Find(u[p.x][p.y])) { p.x++; q.push(p); p.x--; Union(u[p.x+1][p.y],u[p.x][p.y]); } if(!vis[p.x][p.y-1]&&p.y>1&&a[p.x][p.y-1]!=a[p.x][p.y]) if(Find(u[p.x][p.y-1])!=Find(u[p.x][p.y])) { p.y--; q.push(p); p.y++; Union(u[p.x][p.y-1],u[p.x][p.y]); } if(!vis[p.x][p.y+1]&&p.y<n&&a[p.x][p.y+1]!=a[p.x][p.y]) if(Find(u[p.x][p.y+1])!=Find(u[p.x][p.y])) { p.y++; q.push(p); p.y--; Union(u[p.x][p.y+1],u[p.x][p.y]); } } for(int i=1;i<=k;i++) vis[t[i].x][t[i].y]=ans; vis[x][y]=ans; return ans; } int main() { memset(vis,0,sizeof(vis)); scanf("%d%d",&n,&m); for(int i=1;i<=n*n;i++) s[i]=i; turn(n); char c; scanf("\n"); for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { c=getchar(); a[i][j]=c-'0'; } scanf("\n"); } int x,y; for(int i=1;i<=m;i++) { scanf("%d%d",&x,&y); printf("%d\n",bfs(x,y)); } return 0; } ```