1063B - Labyrinth - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
const int N=2005;
char a[N][N];
int disx[N][N],disy[N][N],vis[N][N];
int n,m,x,y,limx,limy;
struct point
{
	int x,y;
	int cntx,cnty;
};
int ans=0;
int dx[4]={0,1,-1,0},dy[4]={-1,0,0,1};//左下上右
bool check(int x,int y)
{
	if(x>=0&&x<n&&y>=0&&y<m) return true;
	else return false;
 } 
void bfs(int x,int y)
{
	memset(disx,0x3f,sizeof(disx));
	memset(disy,0x3f,sizeof(disy));//初始化 
	queue<point> q;
	q.push((point){x,y,0,0});
	disx[x][y]=disy[x][y]=0;//起点处理
	while(!q.empty())
	{
		point tmp=q.front();
		q.pop();
		x=tmp.x,y=tmp.y;
		for(int i=0;i<=3;i++)
		{
			int nx=x+dx[i];
			int ny=y+dy[i];
			if( !check(nx,ny) || a[nx][ny]=='*')
			{
				continue;//出界或不能走 就跳过 
			}
			int cntx=tmp.cntx+ bool(dy[i]==-1);//向左的步数 
			int cnty=tmp.cnty+ bool(dy[i]==1);//向右
			if(cntx<min(disx[nx][ny],limx+1)||cnty<min(disy[nx][ny],limy+1))//剪枝，记到这个点的最小步数 
			{
				disx[nx][ny]=cntx;
				disy[nx][ny]=cnty;
				q.push((point){nx,ny,cntx,cnty});
			} 
		}
	 } 
}
int main()
{
	cin>>n>>m>>x>>y>>limx>>limy;
	x--,y--;//变为（0，0）开头的矩阵 
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			cin>>a[i][j];
		}
	}
	bfs(x,y);
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)//遍历每个点看能否走到 
		{
			if(disx[i][j]<=limx && disy[i][j]<=limy)
			{
				ans++;
			}
		}
	}
	cout<<ans;
	return 0;
}