题意：M行N列的矩阵。Y：起点，T：终点。S、R不能走，走B花费2，走E花费1.求Y到T的最短时间。
三种解法。♪(^∇^*)
//解法一：暴力
//157MS #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<string> #include<cmath> #include<queue> #include<limits.h> #define CLR(a,b) memset((a),(b),sizeof((a))) using namespace std; typedef long long ll; const int inf = 0x3f3f3f3f; const int mod = 1e9+7; const int N = 305; int a[N][N], b[N][N]; char s[N][N]; int m, n; int main() { int i, j; while(~scanf("%d%d", &m, &n), n || m) { getchar(); int sx, sy, ex, ey; for(i = 0; i < m; ++i) scanf("%s", s[i]); for(i = 0; i < m; ++i) { for(j = 0; j < n; ++j) { if(s[i][j] == 'R' || s[i][j] == 'S') a[i][j] = inf; else if(s[i][j] == 'B') a[i][j] = 2; else a[i][j] = 1; if(s[i][j] == 'Y') {sx = i; sy = j;} else if(s[i][j] == 'T') {ex = i; ey = j;} } } CLR(b, inf); b[sx][sy] = 0; while(1) { bool f = 0; for(i = 0; i < m; ++i) { for(j = 0; j < n; ++j) { if(b[i][j] == inf) continue; if(i > 0 && b[i-1][j] > b[i][j] + a[i-1][j]) { b[i-1][j] = b[i][j] + a[i-1][j]; f = 1; } if(i < m-1 && b[i+1][j] > b[i][j] + a[i+1][j]) { b[i+1][j] = b[i][j] + a[i+1][j]; f = 1; } if(j > 0 && b[i][j-1] > b[i][j] + a[i][j-1]) { b[i][j-1] = b[i][j] + a[i][j-1]; f = 1; } if(j < n-1 && b[i][j+1] > b[i][j] + a[i][j+1]) { b[i][j+1] = b[i][j] + a[i][j+1]; f = 1; } } } if(!f) break; } if(b[ex][ey] != inf) printf("%d ", b[ex][ey]); else printf("-1 "); } return 0; }
//解法二：bfs+优先队列
//16MS #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<string> #include<cmath> #include<queue> #include<limits.h> #define CLR(a,b) memset((a),(b),sizeof((a))) using namespace std; typedef long long ll; const int inf = 0x3f3f3f3f; const int mod = 1e9+7; const int N = 305; struct node { int x, y; int w; node(int x = 0, int y = 0, int w = 0):x(x),y(y),w(w){} bool operator < (const node&r) const { return w > r.w; } }; char s[N][N]; bool vis[N][N]; int dx[] = {1,0,-1,0}; int dy[] = {0,1,0,-1}; int m, n; int ans; int sx, sy; bool check(int x, int y) { if(x < 0 || x >= m || y < 0 || y >= n) return false; if(s[x][y] == 'S' || s[x][y] == 'R' || vis[x][y]) return false; return true; } int bfs() { CLR(vis, 0); priority_queue<node> q; q.push(node(sx, sy, 0)); vis[sx][sy] = 1; while(!q.empty()) { node t = q.top(); q.pop(); //vis[t.x][t.y] = 0; if(s[t.x][t.y] == 'T') { ans = t.w; return true; } for(int i = 0; i < 4; ++i) { int x = t.x + dx[i]; int y = t.y + dy[i]; if(check(x, y)) { int w = t.w + 1; if(s[x][y] == 'B') w++; vis[x][y] = 1; q.push(node(x, y, w)); } } } return false; } int main() { int i, j; while(~scanf("%d%d", &m, &n), n || m) { getchar(); for(i = 0; i < m; ++i) scanf("%s", s[i]); for(i = 0; i < m; ++i) { for(j = 0; j < n; ++j) { if(s[i][j] == 'Y') {sx = i; sy = j; break;} } } if(bfs()) printf("%d ", ans); else printf("-1 "); } return 0; }
//解法三：bfs，不用优先队列，搜到B时，把它变换成E再放入队列，重新取下一个队首继续搜索，这样就不用优先队列，用普通队列也能做啦
//32MS #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<string> #include<cmath> #include<queue> #include<limits.h> #define CLR(a,b) memset((a),(b),sizeof((a))) using namespace std; typedef long long ll; const int inf = 0x3f3f3f3f; const int mod = 1e9+7; const int N = 305; struct node { int x, y; int w; node(int x = 0, int y = 0, int w = 0):x(x),y(y),w(w){} }; char s[N][N]; bool vis[N][N]; int dx[] = {1,0,-1,0}; int dy[] = {0,1,0,-1}; int m, n; int ans; int sx, sy; bool check(int x, int y) { if(x < 0 || x >= m || y < 0 || y >= n) return false; if(s[x][y] == 'S' || s[x][y] == 'R' || vis[x][y]) return false; return true; } int bfs() { CLR(vis, 0); queue<node> q; q.push(node(sx, sy, 0)); vis[sx][sy] = 1; while(!q.empty()) { node t = q.front(); q.pop(); if(s[t.x][t.y] == 'T') { ans = t.w; return true; } if(s[t.x][t.y] == 'B') { t.w++; s[t.x][t.y] = 'E'; q.push(t); continue; } for(int i = 0; i < 4; ++i) { int x = t.x + dx[i]; int y = t.y + dy[i]; if(check(x, y)) { int w = t.w + 1; vis[x][y] = 1; q.push(node(x, y, w)); } } } return false; } int main() { int i, j; while(~scanf("%d%d", &m, &n), n || m) { getchar(); for(i = 0; i < m; ++i) scanf("%s", s[i]); for(i = 0; i < m; ++i) { for(j = 0; j < n; ++j) { if(s[i][j] == 'Y') {sx = i; sy = j; break;} } } if(bfs()) printf("%d ", ans); else printf("-1 "); } return 0; }