Submission #64556749

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e3+10,M=1e9;
int h,w,xc,yc,xz,yz;
char a[N][N];
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
int dis[N][N];
struct node
{
  int x,y;
};
deque<node>q;
void bfs()
{
  while(!q.empty())
  {
    int x=q.front().x,y=q.front().y;
    q.pop_front();
    for(int i=0;i<4;i++)
    {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e3+10,M=1e9;
int h,w,xc,yc,xz,yz;
char a[N][N];
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
int dis[N][N];
struct node
{
	int x,y;
};
deque<node>q;
void bfs()
{
	while(!q.empty())
	{
		int x=q.front().x,y=q.front().y;
		q.pop_front();
		for(int i=0;i<4;i++)
		{
			int xnew=x+dx[i],ynew=y+dy[i];
			if(xnew<1||xnew>h||ynew<1||ynew>w||a[xnew][ynew]=='#'||dis[xnew][ynew]<=dis[x][y]) 
			{
				continue;
			}
			q.push_front({xnew,ynew});
			dis[xnew][ynew]=dis[x][y];
		}
		for(int i=x-2;i<=x+2;i++)
		{
			int xnew=i,ynew=y;
			if(xnew<1||xnew>h||ynew<1||ynew>w||dis[xnew][ynew]<=dis[x][y]) 
			{
				continue;
			}
			q.push_back({xnew,ynew});
			dis[xnew][ynew]=dis[x][y]+1;
		}
		for(int i=y-2;i<=y+2;i++)
		{
			int xnew=x,ynew=i;
			if(xnew<1||xnew>h||ynew<1||ynew>w||dis[xnew][ynew]<=dis[x][y]) 
			{
				continue;
			}
			q.push_back({xnew,ynew});
			dis[xnew][ynew]=dis[x][y]+1;
		}
	}
}
signed main()
{
	cin>>h>>w;
	for(int i=1;i<=h;i++)
	{
		for(int j=1;j<=w;j++)
		{
			cin>>a[i][j];
		}
	}
	cin>>xc>>yc>>xz>>yz;
	memset(dis,0x3f,sizeof(dis));
	q.push_front({xc,yc});
	dis[xc][yc]=0;
	bfs();
	cout<<dis[xz][yz];
	return 0;
}

Submission Info

Judge Result