Description Bessie is in Camelot and has encountered a sticky situation: she needs to pass through the forest that is guarded by the Knights of Ni. In ...
Description
Bessie is in Camelot and has encountered a sticky situation: she needs to pass through the forest that is guarded by the Knights of Ni. In order to pass through safely, the Knights have demanded that she bring them a single shrubbery. Time is of the essence, and Bessie must find and bring them a shrubbery as quickly as possible. Bessie has a map of of the forest, which is partitioned into a square grid arrayed in the usual manner, with axes parallel to the X and Y axes. The map is W x H units in size (1 <= W <= 1000; 1 <= H <= 1000). The map shows where Bessie starts her quest, the single square where the Knights of Ni are, and the locations of all the shrubberies of the land. It also shows which areas of the map can be traverse (some grid blocks are impassable because of swamps, cliffs, and killer rabbits). Bessie can not pass through the Knights of Ni square without a shrubbery. In order to make sure that she follows the map correctly, Bessie can only move in four directions: North, East, South, or West (i.e., NOT diagonally). She requires one day to complete a traversal from one grid block to a neighboring grid block. It is guaranteed that Bessie will be able to obtain a shrubbery and then deliver it to the Knights of Ni. Determine the quickest way for her to do so.
貝茜遇到了一件很麻煩的事：她無意中闖入了森林里的一座城堡，如果她想回家，就必須穿過這片由騎士們守護著的森林．為了能安全地離開，貝茜不得不按照騎士們的要求，在森林尋找一種特殊的灌木並帶一棵給他們．當然，貝茜想早點離開這可怕的森林，於是她必須儘快完成騎士們給的任務，貝茜隨身帶著這片森林的地圖，地圖上的森林被放入了直角坐標系，並按x,y軸上的單位長度劃分成了W×H(1≤W,H≤1000)塊，貝茜在地圖上查出了她自己以及騎士們所在的位置，當然地圖上也標註了她所需要的灌木生長的區域．某些區域是不能通過的（比如說沼澤地，懸崖，以及食人兔的聚居地）．在沒有找到灌木之前，貝茜不能通過騎士們所在的那個區域，為了確保她自己不會迷路，貝茜只向正北、正東、正南、正西四個方向移動（註意，她不會走對角線）．她要走整整一天，才能從某塊區域走到與它相鄰的那塊區域． 輸入數據保證貝茜一定能完成騎士的任務．貝茜希望你能幫她計算一下，她最少需要多少天才可脫離這可怕的地方？
Input
第1行輸入2個用空格隔開的整數，即題目中提到的W、H.
接下來輸入貝茜持有的地圖，每一行用若幹個數字代表地圖上對應行的地形．第1行描述了地圖最北的那一排土地；最後一行描述的則是最南面的．相鄰的數字所對應的區域是相鄰的．如果地圖的寬小於或等於40，那每一行數字恰好對應了地圖上的一排土地．如果地圖的寬大於40，那每行只會給出40個數字，並且保證除了最後一行的每一行都包含恰好40個數字．沒有哪一行描述的區域分佈在兩個不同的行里．地圖上的數字所對應的地形：
0：貝茜可以通過的空地
1：由於各種原因而不可通行的區域
2：貝茜現在所在的位置
3：騎士們的位置
4：長著貝茜需要的灌木的土地Output
輸出一個正整數D，即貝茜最少要花多少天才能完成騎士們給的任務．Sample Input
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
Sample Output
11
HINT
這片森林的長為8，寬為4．貝茜的起始位置在第3行，離騎士們不遠．
貝茜可以按這樣的路線完成騎士的任務：北，西，北，南，東，東，北，東，東，南，南．她在森林的西北角得到一株她需要的灌木，然後繞過障礙把它交給在東南方的騎士．這題其實並不難想，兩遍bfs，從貝茜的位置跑一遍，再從騎士的位置跑一遍，然後掃到有灌木的點隨便搞一下就可以了
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define inf 0x7f7f7f7f
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
inline int read(){
int x=0,f=1;char ch=getchar();
for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
for (;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+ch-'0';
return x*f;
}
inline void print(int x){
if (x>=10) print(x/10);
putchar(x%10+'0');
}
const int N=1e3;
const int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
int map[N+10][N+10],dis[N+10][N+10],dist[N+10][N+10];
int hx[N*N+10],hy[N*N+10];
int n,m,O1x,O1y,O2x,O2y;
bool in_map(int x,int y){return x>0&&x<=n&&y>0&&y<=m;}
void bfs1(int x,int y){
int head=1,tail=1;
memset(dis,-1,sizeof(dis));
hx[1]=x,hy[1]=y,dis[x][y]=0;
for (;head<=tail;head++){
int Nx=hx[head],Ny=hy[head];
for (int i=0;i<4;i++){
int tx=Nx+dx[i],ty=Ny+dy[i];
if (!in_map(tx,ty)||dis[tx][ty]!=-1||map[tx][ty]==1) continue;
dis[tx][ty]=dis[Nx][Ny]+1;
hx[++tail]=tx,hy[tail]=ty;
}
}
}
void bfs2(int x,int y){
int head=1,tail=1;
memset(dist,-1,sizeof(dist));
hx[1]=x,hy[1]=y,dist[x][y]=0;
for (;head<=tail;head++){
int Nx=hx[head],Ny=hy[head];
for (int i=0;i<4;i++){
int tx=Nx+dx[i],ty=Ny+dy[i];
if (!in_map(tx,ty)||dist[tx][ty]!=-1||map[tx][ty]==1) continue;
dist[tx][ty]=dist[Nx][Ny]+1;
hx[++tail]=tx,hy[tail]=ty;
}
}
}
int work(){
int Min=inf;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++){
if (map[i][j]!=4||dis[i][j]==-1||dist[i][j]==-1) continue;
Min=min(Min,dis[i][j]+dist[i][j]);
}
return Min;
}
int main(){
m=read(),n=read();
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++){
map[i][j]=read();
if (map[i][j]==2) O1x=i,O1y=j;
if (map[i][j]==3) O2x=i,O2y=j;
}
bfs1(O1x,O1y),bfs2(O2x,O2y);
printf("%d\n",work());
return 0;
}
