[kuangbin带你飞]专题一 简单搜索
正确代码：
1 #include<iostream> 2 #include<queue> 3 #define N 210 4 #define inf 0xffffff 5 using namespace std; 6 int m,n,mark[N][N],dis[N][N][2],dir[4][2]={1,0, 0,1, -1,0, 0,-1},flag; 7 char s[N][N]; 8 struct node{ 9 int x,y,step; 10 }; 11 bool judge(int x,int y) 12 { 13 if(x>=0 && x<m && y>=0 && y<n && s[x][y]!='#' && mark[x][y]==0) 14 return 1; 15 return 0; 16 } 17 void bfs(int x,int y) 18 { 19 int k; 20 queue<node>q; 21 node cur,next; 22 cur.x=x;cur.y=y;cur.step=0; 23 mark[x][y]=1; 24 q.push(cur); 25 while(!q.empty()) 26 { 27 cur=q.front(); 28 q.pop(); 29 next.step=cur.step+1; 30 for(k=0;k<4;k++) 31 { 32 next.x=x=cur.x+dir[k][0]; 33 next.y=y=cur.y+dir[k][1]; 34 if(judge(x,y)) 35 { 36 mark[x][y]=1; 37 if(s[x][y]=='@') 38 dis[x][y][flag]=next.step; 39 q.push(next); 40 } 41 } 42 } 43 } 44 45 int main() 46 { 47 int i,j,min; 48 while(scanf("%d %d",&m,&n)!=-1) 49 { 50 min=inf; 51 for(i=0;i<m;i++) 52 for(j=0;j<n;j++) 53 dis[i][j][0]=dis[i][j][1]=inf; 54 55 for(i=0;i<m;i++) 56 scanf("%s",s[i]); 57 for(i=0;i<m;i++) 58 for(j=0;j<n;j++) 59 { 60 if(s[i][j]=='Y') 61 { 62 flag=0; 63 memset(mark,0,sizeof(mark)); 64 bfs(i,j); 65 } 66 else if(s[i][j]=='M') 67 { 68 flag=1; 69 memset(mark,0,sizeof(mark)); 70 bfs(i,j); 71 } 72 } 73 for(i=0;i<m;i++) 74 for(j=0;j<n;j++) 75 if(s[i][j]=='@' && min>dis[i][j][0]+dis[i][j][1]) 76 min=dis[i][j][0]+dis[i][j][1]; 77 printf("%d ",min*11); 78 } 79 return 0; 80 }
被逼疯代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<queue> 6 #define INF 0x3f3f3f3f 7 using namespace std; 8 struct node 9 { 10 int x; 11 int y; 12 int step; 13 }; 14 char g[205][205]; 15 int stepA[205][205]; 16 int stepB[205][205]; 17 queue<node>q; 18 int yx, yy, mx, my; 19 int x, y; 20 long long ans; 21 int d[4][2]={{0,1},{1,0},{0,-1},{-1,0}}; 22 23 int main() 24 { 25 // freopen("in.in","r",stdin); 26 // freopen("out.txt","w",stdout); 27 while(scanf("%d%d",&x,&y)!=EOF) 28 { 29 memset(g,0,sizeof(g)); 30 memset(stepA,-1,sizeof(stepA)); 31 memset(stepB,-1,sizeof(stepB)); 32 char tmp[205]; 33 for(int i = 1; i <= x; i++) 34 { 35 scanf("%s",tmp); 36 for(int j = 1; j <= y; j++) 37 { 38 if(tmp[j-1]=='Y') 39 { 40 yx = i; 41 yy = j; 42 } 43 if(tmp[j-1]=='M') 44 { 45 mx = i; 46 my = j; 47 } 48 g[i][j] = tmp[j-1]; 49 } 50 } 51 ans = INF; 52 53 node s, t; 54 55 s.x = yx; 56 s.y = yy; 57 s.step = 0; 58 q.push(s); 59 while(q.size()) 60 { 61 s = q.front(); 62 q.pop(); 63 stepA[s.x][s.y] = s.step; 64 for(int i = 0; i < 4; i++) 65 { 66 t.x = s.x + d[i][0]; 67 t.y = s.y + d[i][1]; 68 t.step = s.step + 1; 69 if(stepA[t.x][t.y] != -1) continue; 70 if(g[t.x][t.y]=='.'|| g[t.x][t.y]=='@') 71 q.push(t); 72 } 73 } 74 s.x = mx; 75 s.y = my; 76 s.step = 0; 77 q.push(s); 78 while(q.size()) 79 { 80 s = q.front(); 81 q.pop(); 82 stepB[s.x][s.y] = s.step; 83 for(int i = 0; i < 4; i++) 84 { 85 t.x = s.x + d[i][0]; 86 t.y = s.y + d[i][1]; 87 t.step = s.step + 1; 88 if(stepB[t.x][t.y] != -1) continue; 89 if(g[t.x][t.y]=='.'|| g[t.x][t.y]=='@') 90 q.push(t); 91 } 92 } 93 for(int i = 1; i <= x; i++) 94 { 95 for(int j = 1; j <= y; j++) 96 { 97 if(g[i][j]=='@' && stepA[i][j]+stepB[i][j]<ans && stepA[i][j]!=-1 && stepB[i][j]!=-1) 98 ans = stepA[i][j]+stepB[i][j]; 99 } 100 } 101 cout<<ans*11<<endl; 102 } 103 104 return 0; 105 }