HDU 勝利大逃亡（BFS）

Problem Description

Ignatius被魔王抓走了,有一天魔王出差去了,這可是Ignatius逃亡的好機會.
魔王住在一個城堡里,城堡是一個ABC的立方體,可以被表示成A個B*C的矩陣,
剛開始Ignatius被關在(0,0,0)的位置,離開城堡的門在(A-1,B-1,C-1)的位置,現在知道魔王將在T分鐘后回到城堡,
Ignatius每分鐘能從一個坐標走到相鄰的六個坐標中的其中一個.
現在給你城堡的地圖,請你計算出Ignatius能否在魔投訓來前離開城堡(只要走到出口就算離開城堡,如果走到出口的時候魔王剛好回來也算逃亡成功),如果可以請輸出需要多少分鐘才能離開,如果不能則輸出-1.

Input

輸入資料的第一行是一個正整數K,表明測驗資料的數量.每組測驗資料的第一行是四個正整數A,B,C和T(1<=A,B,C<=50,1<=T<=1000),它們分別代表城堡的大小和魔投訓來的時間.然后是A塊輸入資料(先是第0塊,然后是第1塊,第2塊…),每塊輸入資料有B行,每行有C個正整數,代表迷宮的布局,其中0代表路,1代表墻.(如果對輸入描述不清楚,可以參考Sample Input中的迷宮描述,它表示的就是上圖中的迷宮) 特別注意:本題的測驗資料非常大,請使用scanf輸入,我不能保證使用cin能不超時.

Output

對于每組測驗資料,如果Ignatius能夠在魔投訓來前離開城堡,那么請輸出他最少需要多少分鐘,否則輸出-1.

Sample Input

1
3 3 4 20
0 1 1 1
0 0 1 1
0 1 1 1
1 1 1 1
1 0 0 1
0 1 1 1
0 0 0 0
0 1 1 0
0 1 1 0

Sample Output

11

BFS

BFS的核心思路就是物件狀態的轉移，給了你初始節點、終止節點、生成子節點的約束條件，求物件轉移狀態總共花費的最小代價，對于本題，Ignatius的初始狀態是（0，0，0）目標狀態是（A - 1，B - 1，C - 1），狀態轉移的約束條件是：

1. 不能超出迷宮的范圍
2. 迷宮是1的地方不能走
3. 走過的地方不要走（減枝）

最后考慮bfs的出口：走到出口并且沒有超過魔王外出的時間！

總結：不同的題目只不過是狀態轉移的方式和離開的條件不同，思路大致是相同的，

狀態結點

struct node
{
	int x,y,z;
	int step;
};

初始狀態生成

memset(vis,0,sizeof(vis));	//需要include<cstring>,把陣列置0，表示迷宮所有結點未被走過
	node Now,next;			//需要兩個表示狀態的結點，分別用于存盤當前狀態和下一個狀態		
	Now.x = Now.y = Now.z = Now.step = 0;
	vis[0][0][0] = 1;		

	queue<node> q;			//佇列用來保證步數小的狀態一定比步數大的狀態先出隊

	q.push(Now);

回圈出口

if(Now.x == A - 1&& Now.y == B - 1 && Now.z == C - 1) 
		{
			if (Now.step <= time)
				{cout << Now.step << endl;
				return ;}
			else{
				cout << -1 << endl;
				return ;
			}
		}

狀態轉移，判斷部分可以寫成一個函式

for(int i = 0;i < 6; i++){
			next.x = Now.x + dir[i][0];
			next.y = Now.y + dir[i][1];
			next.z = Now.z + dir[i][2];
			if (next.x>=0&&next.x <= A - 1&&next.y>=0&&next.y <= B - 1&&next.z >= 0 && next.z <= C - 1 &&Maze[next.x][next.y][next.z] != 1&&!vis[next.x][next.y][next.z])
			{
				next.step = Now.step + 1;
				vis[next.x][next.y][next.z] = 1;
				q.push(next);
			}
		}

完整代碼

#include<iostream>
#include<queue>
#include<cstring>

using namespace std;

int Maze[51][51][51];			//存盤迷宮
int vis[51][51][51];			//存盤該狀態是否來過了
int dir[6][3] = {{1,0,0},{0,0,1},{-1,0,0},{0,0,-1},{0,1,0},{0,-1,0}};		//狀態轉移陣列
int A, B, C, time;

struct node
{
	int x,y,z;
	int step;
};

void BFS(){
	memset(vis,0,sizeof(vis));
	node Now,next;
	Now.x = Now.y = Now.z = Now.step = 0;
	vis[0][0][0] = 1;

	queue<node> q;

	q.push(Now);

	while (!q.empty()) {
		Now = q.front();
		q.pop();

		if(Now.x == A - 1&& Now.y == B - 1 && Now.z == C - 1) 
		{
			if (Now.step <= time)
				{cout << Now.step << endl;
				return ;}
			else{
				cout << -1 << endl;
				return ;
			}
		}
		for(int i = 0;i < 6; i++){
			next.x = Now.x + dir[i][0];
			next.y = Now.y + dir[i][1];
			next.z = Now.z + dir[i][2];
			if (next.x>=0&&next.x <= A - 1&&next.y>=0&&next.y <= B - 1&&next.z >= 0 && next.z <= C - 1 &&Maze[next.x][next.y][next.z] != 1&&!vis[next.x][next.y][next.z])
			{
				next.step = Now.step + 1;
				vis[next.x][next.y][next.z] = 1;
				q.push(next);
			}
		}
	}
	cout << -1 << endl;
}

int main() {
	int T;
	cin >> T;
	while(T--) {
		cin >> A >> B >> C >> time;
		for(int i = 0;i < A;i++){
			for(int j = 0; j < B; j++){
				for(int k = 0; k < C; k++) {
					scanf("%d",&Maze[i][j][k]);
				}
			}
		}
		BFS();
	}
}