BFS求助,样例全过,提交第23个点RE了
查看原帖
BFS求助,样例全过,提交第23个点RE了
486799
BlackPanda楼主2022/4/8 10:15
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct Node{
	ll x,y,step;
};

ll n,m,k;
ll sx,sy,ex,ey;
char c[1005][1005];
bool vis[1005][1005];
ll xx[]={0,0,1,-1};
ll yy[]={1,-1,0,0};

ll bfs(){
	queue<Node> q;
	Node f,r;
	r={sx,sy,0};
	q.push(r);
	vis[sx][sy]=1;
	while(!q.empty()){
		f=q.front();
		q.pop();
		if(f.x==ex && f.y==ey)
			return f.step;
		for(ll i=0;i<4;i++){
			for(ll j=1;j<=k;j++){
				ll dx=xx[i]*j+f.x;
				ll dy=yy[i]*j+f.y;
				if(c[dx][dy]=='#')	break;
				if(dx>=1&&dx<=n&&dy>=1&&dy<=m&&!vis[dx][dy]){
					vis[dx][dy]=1;
					r={dx,dy,f.step+1};
					q.push(r);
					if(dx==ex && dy==ey)
						return f.step+1;
				}
			}
		}
	}
	return -1;
}

int main(){
	cin>>n>>m>>k;
	for(ll i=1;i<=n;i++){
		for(ll j=1;j<=m;j++){
			cin>>c[i][j];
			if(c[i][j]=='#')	vis[i][j]=1;
		}
	}
	cin>>sx>>sy>>ex>>ey;
	if(sx==ex && sy==ey){
		cout<<0;
		return 0;
	}	
	cout<<bfs();
	return 0;
}


2022/4/8 10:15
加载中...