首页 > 代码库 > War Chess bfs+优先队列
War Chess bfs+优先队列
War chess is hh‘s favorite game:
In this game, there is an N * M battle map, and every player has his own Moving Val (MV). In each round, every player can move in four directions as long as he has enough MV. To simplify the problem, you are given your position and asked to output which grids you can arrive.
In the map:
‘Y‘ is your current position (there is one and only one Y in the given map).
‘.‘ is a normal grid. It costs you 1 MV to enter in this gird.
‘T‘ is a tree. It costs you 2 MV to enter in this gird.
‘R‘ is a river. It costs you 3 MV to enter in this gird.
‘#‘ is an obstacle. You can never enter in this gird.
‘E‘s are your enemies. You cannot move across your enemy, because once you enter the grids which are adjacent with ‘E‘, you will lose all your MV. Here “adjacent” means two grids share a common edge.
‘P‘s are your partners. You can move across your partner, but you cannot stay in the same grid with him final, because there can only be one person in one grid.You can assume the Ps must stand on ‘.‘ . so ,it also costs you 1 MV to enter this grid.
In this game, there is an N * M battle map, and every player has his own Moving Val (MV). In each round, every player can move in four directions as long as he has enough MV. To simplify the problem, you are given your position and asked to output which grids you can arrive.
In the map:
‘Y‘ is your current position (there is one and only one Y in the given map).
‘.‘ is a normal grid. It costs you 1 MV to enter in this gird.
‘T‘ is a tree. It costs you 2 MV to enter in this gird.
‘R‘ is a river. It costs you 3 MV to enter in this gird.
‘#‘ is an obstacle. You can never enter in this gird.
‘E‘s are your enemies. You cannot move across your enemy, because once you enter the grids which are adjacent with ‘E‘, you will lose all your MV. Here “adjacent” means two grids share a common edge.
‘P‘s are your partners. You can move across your partner, but you cannot stay in the same grid with him final, because there can only be one person in one grid.You can assume the Ps must stand on ‘.‘ . so ,it also costs you 1 MV to enter this grid.
InputThe first line of the inputs is T, which stands for the number of test cases you need to solve.
Then T cases follow:
Each test case starts with a line contains three numbers N,M and MV (2<= N , M <=100,0<=MV<= 65536) which indicate the size of the map and Y‘s MV.Then a N*M two-dimensional array follows, which describe the whole map.OutputOutput the N*M map, using ‘*‘s to replace all the grids ‘Y‘ can arrive (except the ‘Y‘ grid itself). Output a blank line after each case.Sample Input
53 3 100....E...Y5 6 4..........PR..E.PY...ETT....TT2 2 100.EEY5 5 2.......P...PYP...P.......3 3 1.E.EYE...Sample Output
....E*.*Y...***..**P*..E*PY...E**....T*.EEY..*...*P*.*PYP*.*P*...*...E.EYE.*.
代码:
#include <iostream>#include <cstring>#include <cstdio>#include <queue>using namespace std;int dir[4][2]={0,1,1,0,0,-1,-1,0};int t,n,m,val,head,tail,tx,ty,d;char map[101][101];int vis[101][101];struct que{ int x,y,mv; friend bool operator <(que a,que b) { return a.mv<b.mv; }}cur;int judge(int x,int y){ if(x<0||y<0||x>=n||y>=m)return 0; return 1;}int check(int x,int y){ for(int i=0;i<4;i++) if(judge(x+dir[i][0],y+dir[i][1])&&map[x+dir[i][0]][y+dir[i][1]]==‘E‘)return 1; return 0;}int check1(int x,int y){ if(vis[x][y]<0)return 0; if(map[x][y]==‘P‘||map[x][y]==‘Y‘)return 0; return 1;}int main(){ priority_queue <que>q; scanf("%d",&t); while(t--) { scanf("%d%d%d",&n,&m,&val); head=tail=0; memset(vis,-1,sizeof(vis)); for(int i=0;i<n;i++) scanf("%s",map[i]); for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { if(map[i][j]==‘Y‘){ cur.x=i,cur.y=j; cur.mv=val; q.push(cur); vis[i][j]=val; break;} } } while(!q.empty()) { for(int i=0;i<4;i++) { tx=q.top().x+dir[i][0]; ty=q.top().y+dir[i][1]; if(!judge(tx,ty)||map[tx][ty]==‘#‘||map[tx][ty]==‘E‘)continue; if(map[tx][ty]==‘T‘)d=q.top().mv-2; else if(map[tx][ty]==‘R‘)d=q.top().mv-3; else d=q.top().mv-1; if(check(tx,ty)&&d>0)d=0; if(d>vis[tx][ty]) { vis[tx][ty]=d; if(d>0) {cur.x=tx; cur.y=ty; cur.mv=d; q.push(cur);} } } q.pop(); } for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { if(check1(i,j))putchar(‘*‘); else putchar(map[i][j]); } cout<<endl; } cout<<endl; }}
War Chess bfs+优先队列
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。