简单BFS。注意最后一组数据，每个初始点不考虑周围是否有敌人。
1 /* 3345 */ 2 #include3 #include 4 #include 5 #include 6 #include 7 using namespace std; 8 9 #define MAXN 105 10 #define INF 0xfffff 11 12 typedef struct node_t { 13 int x, y, e; 14 node_t() {} 15 node_t(int xx, int yy, int ee) { 16 x = xx; y = yy; e = ee; 17 } 18 } node_t; 19 20 char map[MAXN][MAXN]; 21 bool stop[MAXN][MAXN]; 22 int hp[MAXN][MAXN]; 23 int hurt[MAXN][MAXN]; 24 int n, m, mv; 25 int bx, by; 26 int dir[4][2] = { 27 -1,0,0,-1,1,0,0,1 28 }; 29 30 void init() { 31 int i, j, k; 32 33 memset(stop, false, sizeof(stop)); 34 memset(hurt, -1, sizeof(hurt)); 35 for (i=1; i<=n; ++i) { 36 for (j=1; j<=m; ++j) { 37 if (map[i][j] == 'E') { 38 stop[i-1][j] = stop[i][j-1] = stop[i+1][j] = stop[i][j+1] = true; 39 hurt[i][j] = INF; 40 } else if (map[i][j] == 'Y') { 41 bx = i; 42 by = j; 43 } else if (map[i][j] == '.') { 44 hurt[i][j] = 1; 45 } else if (map[i][j] == 'T') { 46 hurt[i][j] = 2; 47 } else if (map[i][j] == 'R') { 48 hurt[i][j] = 3; 49 } else if (map[i][j] == 'P') { 50 hurt[i][j] = 1; 51 } else if (map[i][j] == '#') { 52 hurt[i][j] = INF; 53 } 54 } 55 } 56 } 57 58 bool check(int x, int y) { 59 return x<=0 || x>n || y<=0 || y>m; 60 } 61 62 void bfs() { 63 int x, y, e; 64 int i, j, k; 65 queue Q; 66 node_t nd; 67 68 memset(hp, -1, sizeof(hp)); 69 //if (stop[bx][by] == false) 70 Q.push(node_t(bx,by,mv)); 71 hp[bx][by] = mv; 72 73 while (!Q.empty()) { 74 nd = Q.front(); 75 Q.pop(); 76 77 for (i=0; i<4; ++i) { 78 x = nd.x + dir[i][0]; 79 y = nd.y + dir[i][1]; 80 if (check(x, y)) 81 continue; 82 e = nd.e - hurt[x][y]; 83 if (e > hp[x][y]) { 84 hp[x][y] = e; 85 if (stop[x][y] == false) 86 Q.push(node_t(x, y, e)); 87 } 88 } 89 } 90 } 91 92 void merge() { 93 int i, j, k; 94 95 for (i=1; i<=n; ++i) { 96 for (j=1; j<=m; ++j) { 97 if (hp[i][j]>=0 && map[i][j]!='P') { 98 map[i][j] = '*'; 99 }100 }101 }102 map[bx][by] = 'Y';103 }104 105 int main() {106 int t;107 int i, j, k;108 109 #ifndef ONLINE_JUDGE110 freopen("data.in", "r", stdin);111 freopen("data.out", "w", stdout);112 #endif113 114 scanf("%d", &t);115 while (t--) {116 scanf("%d %d %d", &n, &m, &mv);117 for (i=1; i<=n; ++i)118 scanf("%s", map[i]+1);119 init();120 bfs();121 merge();122 for (i=1; i<=n; ++i)123 printf("%s\n", map[i]+1);124 printf("\n");125 }126 127 return 0;128 }