2023南海区信息学区赛（初中组） T3 步数(原始)

第3题     步数(原始) 查看测评数据信息

有一个二维网格，从上往下，行的编号从1至n，从左往右，列的编号是1至m。

第i行第j列的格子编号为(i,j)，如果 a[i][j]为 '@',表示格子(i,j)有障碍物，

如果a[i][j]为'.'则表示格子(i,j)可通行。

奶牛bessie当前在 格子(r1,c1)，它每一步可以选择往上、下、左、右四个方向之一走 1 至k 格，也就是每一步至少走1格，最多可以走k格。

任何时刻都不能进入障碍物格子，也不能走到网格外面，不能走出界。

问你最少需要多少步才能走到 格子(r2,c2) ，如果不能走到，输出 −1 。

输入格式

第一行，n,m,k。 1<=n,m,k<=1000000,  n*m <= 1000000。

第二行，r1, c1, r2, c2。 1<=r1,r2<=n,  1<=c1,c2<=m。

接下来是n行m列的二维网格a[1..n][1..m]，其中a[i][j]是'@'或'.'。

【提示】

本题测试点数据较大，只有约10%的数据满足n*m<=100

输出格式

一个整数。

输入/输出例子1

输入：

3 5 2

3 2 3 4

.....

.@..@

..@..

输出：

5

输入/输出例子2

输入：

1 6 4

1 1 1 6

......

输出：

2

样例解释

无

分析

和普通广搜没什么区别，就是最短路了，唯一也就是每一步至少走1格，最多可以走k格。

这题毕竟恶心的是数组范围，卡了很久，最终还是开主函数里面了，根据nm的值来定，不开固定的了

同时注意一下剪枝，别超时了，附讲解时的图

同时，不能用vis来剪走过的路，因为可能确定了值但不是最小值！

还有注意起点就是‘@’的情况

#include <bits/stdc++.h>
using namespace std;

const int N=6005;
const int dx[]={-1, 0, 0, 1}, dy[]={0, -1, 1, 0};
struct point
{
	int x, y;
};
long long n, m, k, r1, c1, r2, c2;
queue<point> q;

int main()
{
	scanf("%lld%lld%lld", &n, &m, &k);
	scanf("%lld%lld%lld%lld", &r1, &c1, &r2, &c2);
	
    char mp[n+5][m+5]; //注意！！
    long long dis[n+5][m+5];
    for (int i=1; i<=n; i++)
		scanf("%s", mp[i]+1);
	if (mp[r1][c1]=='@') //注意！
	{
		printf("-1");
		return 0;
	}
    
	int x=r1, y=c1;
	q.push({x, y});
	memset(dis, 63, sizeof dis);
	dis[x][y]=0;
	while (!q.empty())
	{
		point t=q.front();
		q.pop();
		//vis[t.x][t.y]=0;
		for (int j=0; j<4; j++)
		{
			for (int i=1; i<=k; i++)
			{
				int nx=t.x+dx[j]*i, ny=t.y+dy[j]*i; //*i相当于调整走1~k步
				if (nx<1 || nx>n || ny<1 || ny>m) break;
				if (mp[nx][ny]=='@') break;
				if (dis[t.x][t.y]+1>dis[nx][ny]) break;
				//if (vis[nx][ny]) break;
				
				if (dis[nx][ny]>dis[t.x][t.y]+1)
				{
					dis[nx][ny]=dis[t.x][t.y]+1;
					q.push({nx, ny});
				}
                
				//vis[nx][ny]=1;
			}
		}
	}
	/*for (int i=1; i<=n; i++)
	{
		for (int j=1; j<=m; j++)
			cout<<dis[i][j]<<" ";
		cout<<endl;
	}*/
		
	if (dis[r2][c2]==dis[0][0]) printf("-1");
	else printf("%lld", dis[r2][c2]);
	return 0;
}
/*
5 6 4
1 1 2 4
......
.@@.@@
.....@
..@@.@
@....@
*/