/* Name: NYOJ--284--坦克大战 Author: shen_渊 Date: 14/04/17 19:08 Description: 广度优先搜索+优先队列 注意清空地图 对输入地图进行了预处理,将S,R设置为# */ #include<iostream> #include<queue> #include<cstring> using namespace std; const char YOU = 'Y'; const char TARGET = 'T'; const char RIVER = 'R' ; const char SWALL = 'S'; const char BWALL = 'B'; const char EMPOTY = 'E'; const char FORBID = '#'; struct node{ int x,y,steps; node():steps(){}; bool operator <(const node &a)const{ return steps>a.steps; } }you,target; int bfs(); int check(char); ][] = {}; int m,n; ][] = {{,},{,-},{,},{-,}}; int main() { // ios::sync_with_stdio(false); // freopen("in.txt","r",stdin); while(cin>>m>>n, m || n) { int i,j; memset(map,,sizeof(map)); ; i<=m; ++i){ ; j<=n; ++j){ cin>>map[i][j]; switch(map[i][j]){ case YOU:{ you.x = i;you.y = j; break; } case TARGET:{ target.x = i;target.y = j; break; } case RIVER: case SWALL:{ map[i][j] =='#'; break; } default:break; } } } cout<<bfs()<<endl; } ; } int bfs(){ priority_queue<node> Q; while(!Q.empty())Q.pop(); Q.push(you); map[you.x][you.y] = '#'; while(!Q.empty()){ node p = Q.top();Q.pop(); int i,j; ; i<; ++i){ node a; a.x = p.x + dir[i][]; a.y = p.y + dir[i][]; || a.y<|| a.x>m|| a.y>n)continue; int next; if(next = check(map[a.x][a.y])){ a.steps = p.steps + next; if(a.x == target.x && a.y == target.y)return a.steps; Q.push(a); map[a.x][a.y] = '#'; } } } ; } int check(char ch){ switch(ch){ ; ; ; } ; }