hdu 1072 Nightmare
題意：求出Ignatius走出迷宮的時間。
注意：0表示牆，1表示空白，2表示起點，3表示目標點，4表示炸彈時間重置裝置，(1<=n,m<=8)。
思路：這道題如果沒有4，那麼就是一道簡單的深搜。只要不重新走時間裝置就可以了。
/*
思路：
*/
#include
#include
using namespace std;
struct node{
int x;
int y;
int time;// 記錄時間
int step;// 記錄步數
} hero;
/*
n表示行
m表示列
map長度是9，最多輸入8個數據
dir分別表示上下左右,第一個表示(x-1,y+0),x是控制行的
mark記錄英雄第一次走過該點時所剩余的時間
*/
int n,m;
int dir[][2]={{-1,0},{1,0},{0,-1},{0,1}};
int map[9][9];
int main(){
int t;
cin>>t;
void myInput();
void breadthFirstSearch();
while(t--){
cin>>n>>m;
myInput();
breadthFirstSearch();
}
return 0;
}
void myInput(){
for(int i=0;i>map[i][j];
// 找到英雄，記錄他的信息
if(map[i][j]==2){
// 結構體中的整形數據可以直接賦值，字符串就不可以
hero.x=i;
hero.y=j;
hero.time=6;
hero.step=0;
}
}
}
}
void breadthFirstSearch(){
queue que;
// 第一步把hero壓入棧中
que.push(hero);
/*
heroBunshin-英雄分身，這個你懂得，
讓分身去試探，只有正身才會走正確的道路
*/
node heroBunshin,newNode;
while(!que.empty()){
// 第二步彈出頭元素出棧
heroBunshin=que.front();
que.pop();
/*
搜索四面是否可以行動
*/
for(int i=0;i<4;i++){
// 先復制一份
newNode=heroBunshin;
newNode.x=newNode.x+dir[i][0];
newNode.y=newNode.y+dir[i][1];
newNode.step++;
newNode.time--;
//判斷邊界
if(newNode.x>=0&&newNode.y>=0&&newNode.x0){
//走出迷宮，map==3才可以結束程序或著棧內元素全部出棧
if(map[newNode.x][newNode.y]==3){
cout<
Nightmare
惡夢
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 8533 Accepted Submission(s): 4088
Problem Description
Ignatius had a nightmare last night. He found himself in a labyrinth with a time bomb on him.
Ignatius昨天晚上做了一個噩夢。他發現自己身上有一顆炸彈，且自己在迷宮中。
The labyrinth has an exit, Ignatius should get out of the labyrinth before the bomb explodes.
迷宮有一個出口，在炸彈爆炸前Ignatius因該走出迷宮。
The initial exploding time of the bomb is set to 6 minutes.
定時炸彈初始爆炸時間是6秒。
To prevent the bomb from exploding by shake, Ignatius had to move slowly,
為了不使移動過程中炸彈爆炸，Ignatius必須小心的行動，
that is to move from one area to the nearest area(that is, if Ignatius stands on (x,y) now,
假如Ignatius處於（x,y）坐標處，當他要移動到附近的地方時，
he could only on (x+1,y), (x-1,y), (x,y+1), or (x,y-1) in the next minute) takes him 1 minute.
他只能每秒移動到(x+1,y), (x-1,y), (x,y+1), or (x,y-1) 這四點的某一處。
Some area in the labyrinth contains a Bomb-Reset-Equipment.
迷宮的一些地方有炸彈。
They could reset the exploding time to 6 minutes.
他們炸彈的時間是6秒。
Given the layout of the labyrinth and Ignatius' start position,
給出迷宮的布局和一個Ignatius的起點，
please tell Ignatius whether he could get out of the labyrinth,
請寫一個程序告訴Ignatius他是否可以走出迷宮，
if he could, output the minimum time that he has to use to find the exit of the labyrinth, else output -1.
如果他可以，請輸出他走出迷宮的時間，否則輸出-1；
Here are some rules:
游戲規則如下：
1. We can assume the labyrinth is a 2 array.
我們可以認為迷宮是一個2維數組。
2. Each minute, Ignatius could only get to one of the nearest area, and he should not walk out of the border, of course he could not walk on a wall, too.
每一秒Ignatius只能移動一步，且是臨近的位置，他不能走出邊界，當然他也不能再牆上走。
3. If Ignatius get to the exit when the exploding time turns to 0, he can't get out of the labyrinth.
當炸彈爆炸前，如果Ignatius沒有走出了迷宮，那麼Ignatius也就不能走出迷宮。
4. If Ignatius get to the area which contains Bomb-Rest-Equipment when the exploding time turns to 0, he can't use the equipment to reset the bomb.
當炸彈為0時，如果Ignatius走到有重置炸彈的地方，這時他不能重新設定炸彈爆炸的時間，可以說他死定了。
5. A Bomb-Reset-Equipment can be used as many times as you wish, if it is needed, Ignatius can get to any areas in the labyrinth as many times as you wish.
如果可以任意使用炸彈重置裝置，Ignatius可以任意調節時間。
6. The time to reset the exploding time can be ignore, in other words,
換句話說，可以忽略時間重置爆炸時間，
if Ignatius get to an area which contain Bomb-Rest-Equipment, and the exploding time is larger than 0, the exploding time would be reset to 6.
如果Ignatius走到一個重置炸彈的區域，炸彈的時間大於0，那麼爆炸的時間將重置為6。
Input
The input contains several test cases.
輸入語句包含多組測試事件。
The first line of the input is a single integer T which is the number of test cases.
輸入的第一行有一個整數T，他表示測試事件的個數。
T test cases follow.
接下來輸入T個測試數據。
Each test case starts with two integers N and M(1<=N,Mm=8) which indicate the size of the labyrinth.
每一個測試事件的起始行包含兩個整數N和M（1<=n,m<=8），表示迷宮的大小。
Then N lines follow, each line contains M integers.
接下來再輸入N行數據，每一行都有M個整數。
The array indicates the layout of the labyrinth.
數組表示迷宮的布局。
There are five integers which indicate the different type of area in the labyrinth:
在迷宮中有五種數據，分別表示如下：
0: The area is a wall, Ignatius should not walk on it.
0表示牆，Ignatius不能在上面移動。
1: The area contains nothing, Ignatius can walk on it.
1表示什麼東西也沒有，Ignatius可以任意移動。
2: Ignatius' start position, Ignatius starts his escape from this position.
2表示Ignatius的起始位置，也是Ignatius的逃亡起始點。
3: The exit of the labyrinth, Ignatius' target position.
3表示迷宮的出口，Ignatius的目標位置。
4: The area contains a Bomb-Reset-Equipment, Ignatius can delay the exploding time by walking to these areas.
4表示一顆定時炸彈時間重置器，當Ignatius走在上面後可以重新設置爆炸時間。
Output
For each test case, if Ignatius can get out of the labyrinth, you should output the minimum time he needs, else you should just output -1.
對於每一個測試事件，如果Ignatius可以走出迷宮，你應該輸出他走出迷宮的時間，否則輸出-1；
Sample Input3
3 3
2 1 1
1 1 0
1 1 3
4 8
2 1 1 0 1 1 1 0
1 0 4 1 1 0 4 1
1 0 0 0 0 0 0 1
1 1 1 4 1 1 1 3
5 8
1 2 1 1 1 1 1 4
1 0 0 0 1 0 0 1
1 4 1 0 1 1 0 1
1 0 0 0 0 3 0 1
1 1 4 1 1 1 1 1
Sample Output
4
-1
13
Author Ignatius.L
