Submission #3790947

---

Source Code Expand

#include <bits/stdc++.h>
#define int long long
#define INF 1000000007
#define SMO -1000000007
#define P pair<int,int>
using namespace std;
bool prime(int n){
	for(int i=2;i<=sqrt(n);i++){
		if(n%i==0)return false;
	}
	return n!=1;
}
int kaicnt;
int kai(int n,int x){
	kaicnt++;
	if(kaicnt==x){
		kaicnt=0;
		return n%INF;
	}
	return (kai(n-1,x)%INF*n)%INF;
}
int conbi(int n,int x){
	x=min(x,n-x+1);
	return kai(n,x)/kai(x,x);
}
int pow_mod(int n,int k,int m){
	if(k==0)return 1;
	else if(k%2==1)return pow_mod(n,k-1,m)*n%m;
	else {
		int t=pow_mod(n,k/2,m);
		return t*t%m;
	}
}
int l,m,sx,sy,gx,gy;
int hox[5]={0,1,0,-1},hoy[5]={1,0,-1,0};
char c[105][105];
int d[105][105];
int bfs(){
	queue<P>que;
	que.push({sx,sy});
	for(int i=1;i<=l;i++){
		for(int j=1;j<=m;j++)d[i][j]=INF;
	}
	d[sx][sy]=0;
	while(!que.empty()){
		P p=que.front();
		que.pop();
		if(p.first==gx&&p.second==gy)break;
		for(int i=0;i<4;i++){
			int nx=p.first+hox[i],ny=p.second+hoy[i];
			if(nx<=l&&nx>0&&ny<=m&&ny>0&&d[nx][ny]==INF&&c[nx][ny]!='#'){
				que.push({nx,ny});
				d[nx][ny]=d[p.first][p.second]+1;
			}
		}
	}
	return d[gx][gy];
}
signed main(){
	cin>>l>>m>>sx>>sy>>gx>>gy;
	for(int i=1;i<=l;i++){
		for(int j=1;j<=m;j++)cin>>c[i][j];
	}
	cout<<bfs()<<endl;
}

Submission Info

Judge Result