这个题的意思是给你一个方格， X代表房子， .代表空， 在连通的X之间行走不需要花费， 给你起点坐标和终点坐标， 问从起点到终点的最少花费？ 对于这个我们可以使用双bfs来解决这个问题， 即遇到了X就用bfs2来填充， 边界又放入bfs1中更新， 代码如下：
#include <cstdio> #include <cstring> #include <algorithm> #include <queue> using namespace std; int debug[1000+10][1000+10]; int m, n; //m行 n列 char Map[1000+100][1000+100]; int x0, y0, x1, y1; int dx[] = {0, 0, 1, -1}; int dy[] = {1, -1, 0, 0}; bool inside(int x, int y) { return (x>=1&&x<=m&&y>=1&&y<=n); } struct P { int x, y, dis;}; queue<P> que1, que2; bool vis[1000+10][1000+10]; void bfs(int x, int y, int dis) { while(!que2.empty()) que2.pop(); que2.push((P){x, y, dis}); while(!que2.empty()) { P tp = que2.front(); que2.pop(); debug[tp.x][tp.y] = tp.dis; ///////////////// for(int i=0; i<4; i++) { int nx = tp.x+dx[i], ny = tp.y+dy[i]; if(inside(nx, ny)&&!vis[nx][ny]) { if(Map[nx][ny] == 'X') que2.push((P){nx, ny, dis}); else { que1.push((P){nx, ny, dis+1}); //printf("push que1: %d %d %d ", nx, ny, dis+1); } vis[nx][ny] = 1; } } } } int main() { while(scanf("%d%d", &m, &n)==2) { if(n==0 && m==0) break; for(int i=1; i<=m; i++) scanf("%s", Map[i]+1); scanf("%d%d", &x0, &y0); scanf("%d%d", &x1, &y1); while(!que1.empty()) que1.pop(); memset(vis, 0, sizeof(vis)); memset(debug, -1, sizeof(debug)); bfs(x0, y0, 0); int res = -1; while(!que1.empty()) { P tp = que1.front(); que1.pop(); debug[tp.x][tp.y] = tp.dis; //////////////////// for(int i=0; i<4; i++) { int nx = tp.x+dx[i], ny = tp.y+dy[i]; int dis = tp.dis; if(inside(nx, ny) && !vis[nx][ny]) { if(Map[nx][ny] == 'X') bfs(nx, ny, dis); else { que1.push((P){nx, ny, dis+1}); } vis[nx][ny] = 1; } } } // for(int i=1; i<=m; i++) // { // for(int j=1; j<=n; j++) printf("%d ", debug[i][j]); // printf(" "); // } printf("%d ", debug[x1][y1]); } return 0; }