P1141 01迷宫

2019-11-11 05:22:06

字体：大中小

来源：转载

供稿：网友

题见洛谷

#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<string>#include<cmath>#include<vector>bool f[1005][1005];char a[1005][1005];int dx[]={0,0,0,1,-1};int dy[]={0,1,-1,0,0};int n,m;int num[1009][1009];using namespace std;struct H{ int x; int y;}pos[1000*1000+100];int bfs(int kx,int ky){ int head=0,tail=1; if(!num[kx][ky]){ pos[head+1].x=kx,pos[head+1].y=ky;f[kx][ky]=true; while(head<tail){ head++; for(int i=1;i<=4;i++){ int nx=pos[head].x+dx[i],ny=pos[head].y+dy[i]; if(nx<=n&&nx>=1&&ny<=n&&ny>=1) if(a[nx][ny]!=a[pos[head].x][pos[head].y]&&!f[nx][ny]){ pos[++tail].x=nx;pos[tail].y=ny;f[nx][ny]=true; } } } for(int i=1;i<=tail;i++)num[pos[i].x][pos[i].y]=tail;//记忆化 } return num[kx][ky];}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++) cin>>a[i][j]; } for(int i=1;i<=m;i++){ //memset(f,false,sizeof(f));记忆化,不用memset,否则超时 int ax,ay; scanf("%d%d",&ax,&ay); PRintf("%d/n",bfs(ax,ay)); } return 0; }

上一篇：对类的包装尝试

下一篇：双向链表