这是地址
题意就是精简版的坦克大战。。 有草地 打不坏的墙 打的坏的墙 你 和 坦克 特殊优化的BFS 其实是spfa
注意 打的坏的墙代价为2 //打坏 + 走过去 其他的能走的都是1
#include <iostream> #include <cstring> #include <cstdio> #include <queue> #include <algorithm> using namespace std; int dx[] = {0,1,0,-1}; int dy[] = {1,0,-1,0}; const int MAXN = 505; int m,n,x1,x2,y1,y2; char h,num[MAXN][MAXN]; bool viv[MAXN][MAXN]; struct edge{ int x,y,ans; bool friend operator < (edge a,edge b){ return a.ans > b.ans; } }; priority_queue < edge > q; void init(){ memset(num,0,sizeof(num)); memset(viv,0,sizeof(viv)); x1 = x2 = y1 = y2 = 0; return; } bool out(int x,int y){ if(x < 1 || x > n || y < 0 || y >= m || num[x][y] == 'S' || num[x][y] == 'R' || viv[x][y]) return false; else return true; } int dqs(){ while(!q.empty()) q.pop(); q.push((edge){x1,y1,0}); viv[x1][y1] = true; while(!q.empty()){ edge u = q.top(); q.pop(); if(u.x == x2 && u.y == y2) return u.ans; for(int i = 0; i < 4; i ++){ int tx = dx[i] + u.x; int ty = dy[i] + u.y; if(!out(tx,ty)) continue; if(num[tx][ty] == 'B') q.push((edge){tx,ty,u.ans + 2}); else q.push((edge){tx,ty,u.ans + 1}); viv[tx][ty] = true; } } return -1; } int main(){ while(scanf("%d %d",&n,&m) && m && n){ if(m == 0 && n == 0) break; init(); h = getchar(); for(int i = 1; i <= n; i ++) gets(num[i]); for(int i = 1; i <= n; i ++) for(int j = 0; j < m; j ++){ if(num[i][j] == 'Y') x1 = i,y1 = j; else if(num[i][j] == 'T') x2 = i,y2 = j; } printf("%d\n",dqs()); } return 0; }