ni解题报告
题目大意：
贝茜需要通过一个被Ni的骑士守卫的树林。贝茜必须尽可能快的找到一个灌木并且给骑士带去。贝茜有树林的地图，地图大小是W*H（1〈=W〈=1000；1〈=H〈=1000）。贝茜只可以沿着四个方向走：北，东，南，或者西（不能对角）。她从一个格子走到相邻的格子需要花费1天时间。保证贝茜可以拿到一个灌木然后交给Ni的骑士。求确定最快的路线。
地图上的整数描述:
0:贝茜可以通过;
1:贝茜不可以通过;
2:贝茜开始的位置;
3:Ni的骑士位置;
4:灌木的位置;
输入样例:
8 4
4 1 0 0 0 0 1 0
0 0 0 1 0 1 0 0
0 2 1 1 3 0 4 0
0 0 0 4 1 1 1 0
输出样例：
11
样例解释：N, W, N, S, E, E, N, E, E, S, S
解题思路：
这道题明显就是麻烦的宽度搜索啦。（实在是太麻烦了o(>﹏<)o）首先求贝茜到各个灌木的距离，然后就求Ni的骑士到各个灌木的距离，两者相加就是符合题目的路线，求个最小值，输出，搞定！（看上去好像很简单，其实不然！！！）
参考程序：
# include <iostream>
# include <stdio.h>
using namespace std;
const int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
int n,m,a[1005][1005],s[1005][1005];
bool f[1005][1005],f2[1005][1005];
struct data
{
int x,y,t;
}open[1000*1000+100];
void bfs(int x,int y)
{
int h=1,t=1;
open[1].x=x; open[1].y=y; open[1].t=0;
for (;h<=t;h++)
{
for (int i=0; i<4; i++)
{
int nx=open[h].x+dx[i],ny=open[h].y+dy[i];
if (nx<0 || ny<0 || nx>=n || ny>=m || !f[nx][ny]) continue;
f[nx][ny]=false;
if (a[nx][ny]==4)
{
s[nx][ny]=open[h].t+1;
continue;
}
t++; open[t].x=nx; open[t].y=ny; open[t].t=open[h].t+1;
}
}
} // 宽度搜索出贝茜到各个灌木的距离
int main()
{
int mx[3000],my[3000];
int sx,sy,fx,fy;
cin>>m>>n;
for (int i=0; i<n; i++)
for (int j=0; j<m; j++)
{
int c;
cin>>a[i][j];
f[i][j]=f2[i][j]=true;
if (a[i][j]==1) f[i][j]=f2[i][j]=false;
else if (a[i][j]==2) { sx=i; sy=j; }
else if (a[i][j]==3) { fx=i; fy=j; }
s[i][j]=0x7ffffff;
}
int ans=0x7fffff;
bfs(sx,sy);
int h=1,t=1;
open[1].x=fx; open[1].y=fy; open[1].t=0;
for (;h<=t;h++)
{
for (int i=0; i<4; i++)
{
int nx=open[h].x+dx[i],ny=open[h].y+dy[i];
if (a[nx][ny]==4) { ans=min(ans,s[nx][ny]+open[h].t+1); continue; }
if (nx<0 || ny<0 || nx>=n || ny>=m || !f2[nx][ny]) continue;
f2[nx][ny]=false;
t++; open[t].x=nx; open[t].y=ny; open[t].t=open[h].t+1;
}
} // 求Ni的骑士到各个灌木的距离
cout<<ans<<endl;
return 0;
}