C++ 解法, 执行用时: 176ms, 内存消耗: 6264K, 提交时间: 2021-11-11 14:53:55

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <cstring>
#include <string>
#include <map>
#include <set>
#include <iostream>
#include <ctime>

using namespace std;

const int N = 1024;

struct node{
	int x,y,life;
	node(){}
	node(int x,int y,int life = 0) :
		x(x),y(y),life(life) {}
}s,t,boss;

int n,m,k;
char cmap[N][N];

int dx[4] = {1,-1,0,0}; //上下左右
int dy[4] = {0,0,-1,1};
int maxLife[N][N];
bool safe[N][N];

void getSafeArea();
/*
通过观察可以发现
存在一些固定区域魔球无法到达(安全区域)
所以先模拟魔球的扩散处理出这些区域
*/
bool isReachable();
/*
当勇者不在安全区域中时
相邻的两圈魔球到马也怪(圆心)的半径之差为k + 1(即有k格没有魔球)
若勇者朝着靠近马也怪方向移动，则勇者与魔球相向而行
勇者最多可以走 (k - 1) / 2 回合
若勇者朝着远离马也怪方向移动，则勇者与魔球同向而行
勇者可以走无限多回合
*/

inline bool isLegal(int px,int py){
	if(px < 0 || py < 0 || px >= n || py >= m) return false;
	if(cmap[px][py] == 'A' || cmap[px][py] == '#') return false;
	return true;
}

int main(){

	/*freopen("8.in","r",stdin);
	clock_t st,ed;
	st = clock();*/

	scanf("%d %d %d",&n,&m,&k);
	for(int i = 0;i < n;i++){
		scanf("%s",cmap[i]);
		for(int j = 0;j < m;j++){
			if(cmap[i][j] == 'S') s = node(i,j);
			else if(cmap[i][j] == 'T') t = node(i,j);
			else if(cmap[i][j] == 'A') boss = node(i,j);
		}
	}
	getSafeArea();
	printf("%s\n",isReachable() ? "YES" : "NO");

	/*ed = clock();
	printf("%lf\n",(double)(ed - st) / CLOCKS_PER_SEC);
	fclose(stdin);*/
	
	return 0;
}

void getSafeArea(){
	queue <node> q;
	q.push(boss);
	while(!q.empty()){
		node cur = q.front();
		q.pop();
		safe[cur.x][cur.y] = true;

		int px,py;
		if(cur.x >= boss.x){
			px = cur.x + dx[0];
			py = cur.y + dy[0];
			if(isLegal(px,py) && !safe[px][py]){
				safe[px][py] = true;
				q.push(node(px,py));
			}
		}
		if(cur.x <= boss.x){
			px = cur.x + dx[1];
			py = cur.y + dy[1];
			if(isLegal(px,py) && !safe[px][py]){
				safe[px][py] = true;
				q.push(node(px,py));
			}
		}
		if(cur.y <= boss.y){
			px = cur.x + dx[2];
			py = cur.y + dy[2];
			if(isLegal(px,py) && !safe[px][py]){
				safe[px][py] = true;
				q.push(node(px,py));
			}
		}
		if(cur.y >= boss.y){
			px = cur.x + dx[3];
			py = cur.y + dy[3];
			if(isLegal(px,py) && !safe[px][py]){
				safe[px][py] = true;
				q.push(node(px,py));
			}
		}
	}
}
bool isReachable(){
	//memset(maxLife,-1,sizeof(maxLife));
	maxLife[s.x][s.y] = k;
	queue <node> q;
	q.push(node(s.x,s.y,k));
	while(!q.empty()){
		node cur = q.front();
		q.pop();

		if(cur.x == t.x && cur.y == t.y) return true;

		for(int i = 0;i < 4;i++){
			int px = cur.x + dx[i];
			int py = cur.y + dy[i];
			int life = cur.life;

			if(!isLegal(px,py)) continue;
			if(abs(px - boss.x) + abs(py - boss.y) < abs(cur.x - boss.x) + abs(cur.y - boss.y)) life -= 2;
			if(!safe[px][py]) life = k;
			if(life <= 0 || life <= maxLife[px][py]) continue;
			
			maxLife[px][py] = life;
			q.push(node(px,py,life));
		}
	}
	return false;
}