题目翻译

都玩过象棋吧，这题就是一个车追你，但这车由于被诅咒了,所以只能一步一步走或不走，但攻击方式和范围不变，一样的不能穿墙，问你能活吗?

好了也不说其他废话了。

思路

1. $BFS$ 车的能走的范围用 $v_{ij}$ 标记，然后每走一步横竖都判断一下。

2.同样的 $BFS$ 车的能走的范围和攻击范围用 $v_{ij}$ 标记，然后每走一步就只用判断当前点位了。

总结

这道题可能思维难度不高，就是可能代码容易出现出现细节错误，请注意。

附加一句我就只用了第一种，第二种也不难。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
int vi[705][705],p1[705][705],p2[705][705],len[705][705],x,y,xx,yy,xxx,yyy;
char ma[705][705];
struct no{
	int u,v,w;
};
queue<no> q,p;
void bfs(int u,int v,int w){
	if(ma[u][v]=='I'||u>n||v>m||u<1||v<1||vi[u][v])return ;
	len[u][v]=w;
	q.push({u,v,w});
	vi[u][v]=1;
}
void bfs2(int u,int v,int w){
	if(ma[u][v]=='I'||u>n||v>m||u<1||v<1||vi[u][v])return ;
	if(w!=0){
		for(int i=v;i<=m;i++){
			if(ma[u][i]=='I')break;
			if(w>=len[u][i])return;
		}
		for(int i=v;i>0;i--){
			if(ma[u][i]=='I')break;
			if(w>=len[u][i])return;
		}
		for(int i=u;i<=n;i++){
			if(ma[i][v]=='I')break;
			if(w>=len[i][v])return;
		}
		for(int i=u;i>0;i--){
			if(ma[i][v]=='I')break;
			if(w>=len[i][v])return;
		}
	}
	vi[u][v]=1;
	p.push({u,v,w});
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>ma[i][j];
			if(ma[i][j]=='V')x=i,y=j;
			if(ma[i][j]=='Y')xx=i,yy=j;
			if(ma[i][j]=='T')xxx=i,yyy=j;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			p1[i][j]=p1[i][j-1]+(ma[i][j]=='I'?1:0);
		}
	}
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			p1[j][i]=p1[j-1][i]+(ma[j][i]=='I'?1:0);
		}
	}
	bfs(x,y,0);
	while(!q.empty()){
		int l=q.front().u,r=q.front().v,o=q.front().w;
		bfs(l+1,r,o+1);bfs(l-1,r,o+1);bfs(l,r-1,o+1);bfs(l,r+1,o+1);
		q.pop();
	}
	
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)vi[i][j]=0;
	bfs2(xx,yy,0);
	while(!p.empty()){
		int l=p.front().u,r=p.front().v,o=p.front().w;
		bfs2(l+1,r,o+1);bfs2(l-1,r,o+1);bfs2(l,r-1,o+1);bfs2(l,r+1,o+1);
		p.pop();
	}
	if(vi[xxx][yyy])cout<<"YES";
	else cout<<"NO";
	return 0;
}

此为本蒟蒻第一篇 求管理员大大通过

如果不过，请告诉原因谢谢管理员大大