题目描述
アメンボのすぬけ君は南北 H マス東西 W マスの長方形の形をしたグリッド状の池に住んでいます。北から i 番目、西から j 番目のマスをマス (i,j) とします。
いくつかのマスには蓮の葉が浮かんでおり、すぬけ君はそれらのマスには入ることができません。 cij が @ のときマス (i,j) に蓮の葉が浮かんでいること、.のときそうでないことを表します。
すぬけ君は一回水をかくことで東西南北のいずれかの方向に 1 マス以上 K マス以下移動することができます。 移動の途中に蓮の葉のあるマスがあってはいけません。また、蓮の葉のあるマスや池の外に移動することもできません。
すぬけ君がマス (x1,y1) から (x2,y2) まで移動するのに最小で何回水をかく必要があるか求めてください。 (x1,y1) から (x2,y2) まで移動することができない場合、そのことを指摘してください。
输入格式
入力は以下の形式で標準入力から与えられる。
H W K
x1 y1 x2 y2
c1,1 c1,2 .. c1,W
c2,1 c2,2 .. c2,W
...
cH,1 cH,2 .. cH,W
输出格式
すぬけ君がマス (x1,y1) から (x2,y2) まで移動するのに必要な最小の水かきの回数を出力せよ。 (x1,y1) から (x2,y2) まで移動することができない場合、-1を出力せよ。
题意翻译
你在一个划分为上下 H 行，左右 W 列的长方形网格中，网格从上到下的第 i 行的从左往右第 j 列被编号为 (i,j) ，如果 为
@ ，则 (i,j) 不能通过。
你现在在 (x1,y1)，你每步可以往上下左右走 1 至 K 格，问你最少需要多少步才能走到 (x2,y2) ，如果不能走到，输出 −1 。
输入先是一行三个整数 H,W,K ，再是一行四个整数 x1,y1,x2,y2，接着是 H×W 的字符矩阵，第 i 行 j 列表示 。
输入输出样例
输入 #1
3 5 2
3 2 3 4
.....
.@..@
..@..输出 #1
5输入 #2
1 6 4
1 1 1 6
......输出 #2
2输入 #3
3 3 1
2 1 2 3
.@.
.@.
.@.输出 #3
-1说明/提示
制約
- 1 ≤ H,W,K ≤ 106
- H × W ≤ 106
- 1 ≤ x1,x2 ≤ H
- 1 ≤ y1,y2 ≤ W
- x1 ≠ x2 または y1 ≠ y2
- ci,j は
.または@ - cx1,y1 =
. - cx2,y2 = .
- 入力される数はすべて整数である。
Sample Explanation 1
はじめ、すぬけ君はマス (3,2) にいます。 以下のように 5 回水をかくことでマス (3,4) まで移動することができます。 - マス (3,2) から西に 1 マス進み、マス (3,1) に移動する。 - マス (3,1) から北に 2 マス進み、マス (1,1) に移動する。 - マス (1,1) から東に 2 マス進み、マス (1,3) に移動する。 - マス (1,3) から東に 1 マス進み、マス (1,4) に移動する。 - マス (1,4) から南に 2 マス進み、マス (3,4) に移動する。
题目大意
题目背景：
水黾（アメンボ）“すぬけ君”生活在一个呈南北 H 格、东西 W 格的矩形网格状池塘中。我们把从北往南数第 i 行、从西往东数第 j 列的格子称为格子 (i,j)。
池塘中有些格子上漂浮着莲叶，すぬけ君无法进入这些格子。若 的值为 “@”，表示格子 (i,j) 上有莲叶；若其值为 “.”，则表示格子 (i,j) 没有莲叶。
すぬけ君一次划水可以向东、南、西、北任意一个方向移动 1 到 K 格。但移动路径上经过的所有格子都不能有莲叶，且最终落脚的格子也不能有莲叶。同时，不能移动到池塘范围之外。
请计算：すぬけ君从格子 移动到格子
所需的最少划水次数。如果无法从
到
，请指出无法到达。
输入格式：
从标准输入中给出的格式如下：
H W K x1 y1 x2 y2
c1,1 c1,2 … c1,W
c2,1 c2,2 … c2,W
:
cH,1 cH,2 … cH,W- H,W 分别为池塘南北、东西方向的格子数。
- K 为すぬけ君一次划水最多能移动的格子数。
和
分别是起点格子与目标格子的位置（用「北往南数第 x 行，西往东数第 y 列」的方式表示）。
- 接下来的 H 行，每行包含 W 个字符（“@” 或 “.”），表示池塘中每个格子是否有莲叶。
输出格式：
输出すぬけ君从格子 移动到
所需的最少划水次数；若无法到达，请输出
-1。
思路
考虑用 bfs()（广度优先搜索） 做此题。
由于 1 ≤ H,W,K ≤ 106，但没有说明 w，k 的具体大小，所以不能用二维数组存，会爆空间。要改为用一维数组存。
如何表示到下一行呢？只需要加上一个 w 即可。 但是普通的 bfs() 会超时。
容易发现现在队头的坐标 (x,y) 往某个方向走到一定程度时，当前坐标 (x2,y2) 需要走的步数小于现在队头的步数 +1 ，此时就可以停止往这个方向的搜索，因为从 (x2,y2) 已经比从 (x,y) 更优了。以下是最基本的广度优先搜索（bfs()）做这题的步骤：
- 使用 BFS（广度优先搜索）算法求最短路径。每一次水划被视作一步，每个状态是当前所在的格子。
- 对于每个格子，我们尝试向四个方向扩展，步长从1到K。遇到边界、障碍物或者遇到已经用更少或相同次数到达的格子时，就停止当前方向的扩展。
- 用二维数组记录到达每个格子的最少水划次数，初始状态设为极大值。
- 当终点被访问时即输出结果；如果搜索完毕后未能到达终点，则输出-1。
代码
#include<bits/stdc++.h>
using namespace std;
struct stu{int f,s;
};
int ax,h,w,k,x1,yy1/*y1关键字，避坑！！！*/,x2,y2,xx,zz,a[1000010],dx[5]/*一维数组，用来计算一维坐标*/,gx[5]={-1,1,0,0},gy[5]={0,0,-1,1}/*gx,gy表示实际改变的x,y坐标增加了多少*/,ans=1e9;//gy!!!
int vis[1000010];//现在走到一维数组的某个位置最少需要多少步
char c;
queue<int>x,z;//一维坐标和步数
queue<stu>y;//表示实际坐标（可以不用，但更麻烦，会卡常的可以试一下）
stu yy;
void bfs(){while(!x.empty()){xx=x.front(),yy=y.front(),zz=z.front();x.pop(),y.pop(),z.pop();if(xx==(x2-1)*w+y2){ans=min(ans,zz);return ;}for(int i=0;i<4;i++){for(int j=1;j<=k;j++){ax=xx+dx[i]*j;//现在的一维坐标 if(!(yy.f+gx[i]*j>=1&&yy.f+gx[i]*j<=h&&yy.s+gy[i]*j>=1&&yy.s+gy[i]*j<=w))break;if(vis[ax]==zz+1)continue;if(!(vis[ax]>zz+1&&a[ax]))break;//可以通过 vis[ax]=zz+1;x.push(ax),y.push({yy.f+gx[i]*j,yy.s+gy[i]*j}),z.push(zz+1);}} }
}
int main(){cin>>h>>w>>k>>x1>>yy1>>x2>>y2;dx[0]=-w;//上 dx[1]=w;//下dx[2]=-1;//左dx[3]=1;//右 for(int i=1;i<=h*w;i++)vis[i]=1e9;//初始化 for(int i=1;i<=h;i++){for(int j=1;j<=w;j++){cin>>c;if(c=='.')a[(i-1)*w+j]=1;else a[(i-1)*w+j]=0;}}x.push((x1-1)*w+yy1);//一维坐标 y.push({x1,yy1});//二维坐标 z.push(0);vis[(x1-1)*w+yy1]=0;bfs();if(ans==1e9)cout<<-1;else cout<<ans;cout<<endl;return 0;
}
