两年前的坑现在补上，广搜，把点加入优先队列里
#include <stdio.h> #include <string.h> #include <queue> using namespace std; int n,m,total; char mp[108][108],ans[108][108]; int vis[108][108]; int to[4][2] = {1,0,0,1,-1,0,0,-1}; struct Node { int x,y,blood; Node(){} Node(int _x,int _y,int _blood) { x = _x; y = _y; blood = _blood; } bool operator<(const struct Node& oth) const { return blood < oth.blood; } }; bool judge(int x,int y) { if(x < 0 || y < 0 || x >= n || y >= m) return false; return true; } void BFS(int sx,int sy) { bool f; memset(vis,0,sizeof(vis)); int tx,ty,i,bl; struct Node t; priority_queue<Node> pq; pq.push(Node(sx,sy,total)); while(!pq.empty()) { t = pq.top(); pq.pop(); if(t.blood == 0) continue; for(i = 0; i < 4; i++) { tx = t.x + to[i][0]; ty = t.y + to[i][1]; if(!judge(tx,ty)) continue; if(vis[tx][ty]) continue; vis[tx][ty] = 1; if(mp[tx][ty] == '*') continue; f = false; //printf("%d\n",t.blood); if(mp[tx][ty] == '.' && t.blood >= 1) f = true,bl = t.blood - 1,ans[tx][ty] = '*'; else if(mp[tx][ty] == 'T' && t.blood >= 2) f = true,bl = t.blood - 2,ans[tx][ty] = '*'; else if(mp[tx][ty] == 'R' && t.blood >= 3) f = true,bl = t.blood - 3,ans[tx][ty] = '*'; else if(mp[tx][ty] == 'P' && t.blood >= 1) f = true,bl = t.blood - 1; if(f) { if(judge(tx - 1,ty) && mp[tx - 1][ty] == 'E') bl = 0; if(judge(tx,ty - 1) && mp[tx][ty - 1] == 'E') bl = 0; if(judge(tx + 1,ty) && mp[tx + 1][ty] == 'E') bl = 0; if(judge(tx,ty + 1) && mp[tx][ty + 1] == 'E') bl = 0; } if(f) pq.push(Node(tx,ty,bl)); } } } int main(void) { int T,i,j,sx,sy; scanf("%d",&T); while(T--) { scanf("%d %d %d",&n,&m,&total); for(i = 0; i < n; i++) { scanf("%s",mp[i]); strcpy(ans[i],mp[i]); for(j = 0; j < m; j++) { if(mp[i][j] == 'Y') { sx = i; sy = j; } } } BFS(sx,sy); for(i = 0; i < n; i++) printf("%s\n",ans[i]); printf("\n"); } return 0; }
