马里奥 (HG 2018.10.5 T1)
hicc0305
2018-10-05 14:45:36
### 题目大意：
给一个n*m的图，只有'#'和'_','_'是空气，'#'是方块，你一下开始站在最下层(保证最下层都是'#') ，你可以在连续的#上左右移动，上下垂直移动时需要梯子，上下高度差不超过梯子长度的方块可以随意上下。求梯子的最小长度。
### 样例：
输入：
```
5 8
####____
___#_###
###__#__
______#_
########
2 4
```
输出：
2
### 数据范围：
1≤n,m≤1,000，1≤x≤n，1≤y≤m。
那么怎么做呢。。答案是。。爆搜！
dfs会爆栈，要用bfs，搜的时候，记录一下走到现在的梯子用过的最小长度。然后开一个dis数组，表示所有走到x，y这个点的情况中最短的梯子长度。像spfa一样，如果要去的点梯子长度已经还要短了就不走了。具体看代码
```
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,ux,uy;
int dis[1100][1100];
int det[5][3]={{1,0},{0,1},{-1,0},{0,-1}};
char a[1100][1100];
struct Node
{
int x,y,z;
}q[10000100],u,v;
void bfs(int x,int y,int z)
{
u.x=x,u.y=y,u.z=0,q[1]=u;
int l=0,r=1;
while(l<r)
{
u=q[++l];
for(int i=0;i<4;i++)
{
v.x=u.x+det[i][0],v.y=u.y+det[i][1],v.z=u.z;
if(v.x<1 || v.x>n || v.y<1 || v.y>m) continue;
if(i%2)//往左右走
{
if(a[v.x][v.y]=='_') continue;
if(dis[v.x][v.y]<=v.z) continue;
dis[v.x][v.y]=v.z;
q[++r]=v;
}
else//上下爬
{
int l=1;
while(a[v.x][v.y]=='_' && v.x+det[i][0]>=1 && v.x+det[i][0]<=n) l++,v.x+=det[i][0];
if(a[v.x][v.y]=='_' || v.x<1 || v.y>n) continue;
v.z=max(l,v.z);
if(dis[v.x][v.y]<=v.z) continue;
dis[v.x][v.y]=v.z;
q[++r]=v;
}
}
}
}
int main()
{
memset(dis,0x7f,sizeof(dis));
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%s",a[i]+1);
scanf("%d%d",&ux,&uy);
dis[n][m]=0;
bfs(n,1,0);
printf("%d",dis[ux][uy]);
return 0;
}
```