样例能过,数据点31wa了
查看原帖
样例能过,数据点31wa了
817633
Cong_0401楼主2023/10/31 19:26
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

typedef pair<int,int> PII;
queue<pair<int,int> > q;
int n,m,k,x1,y1,x2,y2;
char a[1005][1005];
int d[1005][1005];

int bfs()
{
	x1-=1;y1-=1;x2-=1;y2-=1;
	memset(d,-1,sizeof(d));
	d[x1][y1]=0;
	q.push({x1,y1});
	int dx[4]={-1,0,1,0};
	int dy[4]={0,-1,0,1};
	while(q.size())
	{
		PII t=q.front();
		for(int i=0;i<4;i++)
		{
			for(int j=1;j<=k;j++)
			{
				int x=t.first+dx[i]*j;
				int y=t.second+dy[i]*j;
				if(x>=0 && x<n && y>=0 && y<m && (d[x][y]==-1) && (a[x][y]=='.'))
				{
					q.push({x,y});
					d[x][y]=d[t.first][t.second]+1;
					if(x==x2 && y==y2) return d[x][y];
				}
				else break;
			}
		}
		q.pop();
	}
	return d[x2][y2];
}

int main()
{
	cin>>n>>m>>k;
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			cin>>a[i][j];
	cin>>x1>>y1>>x2>>y2;
	cout<<bfs()<<endl;
	return 0;
}
2023/10/31 19:26
加载中...