90 wa #5
查看原帖
90 wa #5
704089
kkxacj楼主2023/8/16 12:01

rt

#include<bits/stdc++.h>
using namespace std;
long long n,m,x,y,xx,yy,v1[4010][4010],a[10000010],b[10000010],c[10000010],cc[10000010],h,t = 1,ans = 1e9,l;
char d[5010][5010]; 
long long fx[11]={-1,0,1,0};
long long fy[11]={0,1,0,-1};
void bfs()
{
	while(t <= h)
	{
		l = 0;
		for(int i = 0;i < 4;i++)
		{
			if(a[t] + fx[i] > 0 && b[t] + fy[i] > 0 && a[t] + fx[i] <= n && b[t] + fy[i] <= m && !v1[a[t] + fx[i]][b[t] + fy[i]] && d[a[t] + fx[i]][b[t] + fy[i]] != '#')
			{
				l = 1;
				v1[a[t] + fx[i]][b[t] + fy[i]] = 1;
				a[++h] = a[t] + fx[i];
				b[h] = b[t] + fy[i];
				c[h] = c[t] + 1;
				cc[h] = cc[t];
			}	
		}
		for(int i = 4;i <= 4;i++)
			if(!cc[t] && a[t] + fx[i] == n && b[t] + fy[i] == m)
			{
				cout << c[t] + 1;
				exit(0);
			}
		for(int i = 4;i <= 4;i++)
			if(!l && !cc[t] && a[t] + fx[i] > 0 && b[t] + fy[i] > 0 && a[t] + fx[i] <= n && b[t] + fy[i] <= m  && d[a[t] + fx[i]][b[t] + fy[i]] != '#' && !v1[a[t] + fx[i]][b[t] + fy[i]])
			{
				cc[t] = 1;
				v1[a[t] + fx[i]][b[t] + fy[i]] = 1;
				a[++h] = a[t] + fx[i];
				b[h] = b[t] + fy[i];
				c[h] = c[t] + 1;
				cc[h] = cc[t];
			}
		t++;
		if(a[t] == n && b[t] == m)
		{
			cout << c[t];
			exit(0);
		}
	}
	return;
}
int main()
{
	scanf("%lld%lld%lld%lld",&n,&m,&xx,&yy);
	for(int i = 1;i <= n;i++)
		for(int j = 1;j <= m;j++)
			cin >> d[i][j];
	a[++h] = 1; b[h] = 1;
	v1[1][1] = 1;
	fx[4] = xx; fy[4] = yy;
	bfs(); 
	cout << -1;
	return 0;
}
2023/8/16 12:01
加载中...