別人都是廣搜+優先隊列，我沒空臨時學，所以就直接自己暴力了
Ignatius and the Princess I
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 9803 Accepted Submission(s): 2922
Special Judge
Problem Description
The Princess has been abducted by the BEelzebub feng5166, our hero Ignatius has to rescue our pretty Princess. Now he gets into feng5166's castle. The castle is a large labyrinth. To make the problem simply, we assume the labyrinth is a N*M two-dimensional array which left-top corner is (0,0) and right-bottom corner is (N-1,M-1). Ignatius enters at (0,0), and the door to feng5166's room is at (N-1,M-1), that is our target. There are some monsters in the castle, if Ignatius meet them, he has to kill them. Here is some rules:
1.Ignatius can only move in four directions(up, down, left, right), one step per second. A step is defined as follow: if current position is (x,y), after a step, Ignatius can only stand on (x-1,y), (x+1,y), (x,y-1) or (x,y+1).
2.The array is marked with some characters and numbers. We define them like this:
. : The place where Ignatius can walk on.
X : The place is a trap, Ignatius should not walk on it.
n : Here is a monster with n HP(1<=n<=9), if Ignatius walk on it, it takes him n seconds to kill the monster.
Your task is to give out the path which costs minimum seconds for Ignatius to reach target position. You may assume that the start position and the target position will never be a trap, and there will never be a monster at the start position.
Input
The input contains several test cases. Each test case starts with a line contains two numbers N and M(2<=N<=100,2<=M<=100) which indicate the size of the labyrinth. Then a N*M two-dimensional array follows, which describe the whole labyrinth. The input is terminated by the end of file. More details in the Sample Input.
Output
For each test case, you should output "God please help our poor hero." if Ignatius can't reach the target position, or you should output "It takes n seconds to reach the target position, let me show you the way."(n is the minimum seconds), and tell our hero the whole path. Output a line contains "FINISH" after each test case. If there are more than one path, any one is OK in this problem. More details in the Sample Output.
Sample Input
5 6
.XX.1.
..X.2.
2...X.
...XX.
XXXXX.
5 6
.XX.1.
..X.2.
2...X.
...XX.
XXXXX1
5 6
.XX...
..XX1.
2...X.
...XX.
XXXXX.
Sample Output
It takes 13 seconds to reach the target position, let me show you the way.
1s:(0,0)->(1,0)
2s:(1,0)->(1,1)
3s:(1,1)->(2,1)
4s:(2,1)->(2,2)
5s:(2,2)->(2,3)
6s:(2,3)->(1,3)
7s:(1,3)->(1,4)
8s:FIGHT AT (1,4)
9s:FIGHT AT (1,4)
10s:(1,4)->(1,5)
11s:(1,5)->(2,5)
12s:(2,5)->(3,5)
13s:(3,5)->(4,5)
FINISH
It takes 14 seconds to reach the target position, let me show you the way.
1s:(0,0)->(1,0)
2s:(1,0)->(1,1)
3s:(1,1)->(2,1)
4s:(2,1)->(2,2)
5s:(2,2)->(2,3)
6s:(2,3)->(1,3)
7s:(1,3)->(1,4)
8s:FIGHT AT (1,4)
9s:FIGHT AT (1,4)
10s:(1,4)->(1,5)
11s:(1,5)->(2,5)
12s:(2,5)->(3,5)
13s:(3,5)->(4,5)
14s:FIGHT AT (4,5)
FINISH
God please help our poor hero.
FINISH
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
int visit[111][111],n,m,s,xx[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; //visit用來記錄訪問過的點，xx是本人習慣性的方向數組0^^0
char map[111][111]; //map就是輸入的那個地圖
struct ssss
{
int x,y,time;
}ss,up[111][111]; //ss是用來臨時跟隊列內容進行交流的，比如入隊出隊，up就是我的精華了，記錄當前點的指向和時間
queue<ssss> q,qq; //弄倆隊列，後者用來初始化前者的
/*void cmp() //這個是我用來實時監測up數組的變換啊，就是每次隊列的循環我都把整個up打印出來看我的代碼的運作
{
int i,j;
for(i=0;i<n;i++){
for(j=0;j<m;j++)
cout<<up[i][j].x<<up[i][j].y<<up[i][j].time<<" ";cout<<endl;}cout<<endl;
}*/
void bfs()
{
int i,X,x,Y,y,time;
while(!q.empty()) //隊列非空
{
ss=q.front();q.pop(); //用ss取出隊首並刪除隊首
X=ss.x;Y=ss.y;time=ss.time; //用X記錄ss中的x，Y記錄ss中的y，time記錄ss中的time，因為後面要入隊會利用到ss，所以我提前存好數據
if(time) //這個就是其關鍵左右的東西了，簡單吧？只要當前點的時間不是0，那就把時間減一再入隊，嘿嘿，直到時間為0才可以繼續向下走，這就迎合上來題目中的怪物啊，你有多少血，我就陪你入隊多少次，你死了，大爺再前進
{
ss.time=time-1;q.push(ss);continue;
}
if(X==0&&Y==0) //到了起點時就可以處理好並結束廣搜了
{
if(map[X][Y]>'0'&&map[X][Y]<='9') //因為起點可能也有怪物，所以這個步驟也還是少不得的
up[X][Y].time=map[X][Y]-48;
s=1;return;
}
for(i=0;i<4;i++)
{
x=X+xx[i][0];
y=Y+xx[i][1];
if(x>=0&&y>=0&&x<n&&y<m&&visit[x][y]&&map[x][y]!='X') //判斷是否在界內，是否已訪問，是否為陷阱
{
visit[x][y]=0;up[x][y].time=up[X][Y].time+1;ss.time=0; //標記為已訪問，up內的時間+1，入隊的時間初始化為0
if(map[x][y]>'0'&&map[x][y]<='9') //如果是有怪物
up[x][y].time+=map[x][y]-48,ss.time+=map[x][y]-48; //up內的時間再把殺死怪物的時間加上去，入隊的時間就記錄殺死怪物的時間
up[x][y].x=X;up[x][y].y=Y; //把up內的坐標指向處理好，也就是(x,y)是(X,Y)搜索周圍得到的，因此(x,y)要指向(X,Y)
ss.x=x;ss.y=y;q.push(ss); //把入隊的坐標處理好並入隊
}
}
}
}
int main (void)
{
int i,j,k,l,x,y;
while(cin>>n>>m)
{
for(i=0;i<n;i++)
for(j=0;j<m;j++)
cin>>map[i][j],visit[i][j]=1,up[i][j].x=up[i][j].y=up[i][j].time=0; //輸入map並且初始化up數組還有visit
q=qq;ss.x=n-1;ss.y=m-1;ss.time=0;q.push(ss);s=0;visit[n-1][m-1]=0; //初始化隊列，終點的坐標時間打包存入隊列並標記它為已訪問
if(map[n-1][m-1]>'0'&&map[n-1][m-1]<='9')up[n-1][m-1].time=map[n-1][m-1]-48; //終點如果也有怪物，那麼up內的time也要記錄
bfs();
if(s)
{
printf("It takes %d seconds to reach the target position, let me show you the way.\n",up[0][0].time); //因為是從尾到首搜索到，所以時間是從尾到首遞增，所以總時間是記錄在up[0][0]的
i=j=0;l=1; //用i和j從起點回溯，l代表時間
while(i!=n-1||j!=m-1) //一定要用“||”不然可能走到最右邊或者最下邊就會結束的
{
x=up[i][j].x;y=up[i][j].y;k=up[i][j].time-up[x][y].time-1; //x，y記錄下一個點的坐標，k是這點的時間和下一點的時間差減一，因為走一步也要時間的
while(k-->0) //接下來的k分鐘就老老實實留在這裡打怪好了，哦耶～
printf("%ds:FIGHT AT (%d,%d)\n",l++,i,j);
printf("%ds:(%d,%d)->(%d,%d)\n",l++,i,j,x,y);
i=x;j=y;
}
k=up[i][j].time; //完了之後可沒完全完，終點可能是有怪的，所以也要看一看，不然前面就白處理了呗
while(k--)
printf("%ds:FIGHT AT (%d,%d)\n",l++,i,j);
}else puts("God please help our poor hero.");
puts("FINISH");
}
return 0;
}
我是從終點開始向起點廣搜的，因為我從一個點搜索周圍不可能同時指向四個方向啊，就算可以怎麼去區分我要的路線？從起點開始又還要回溯把這條路“打通”懂？本來指向就是單向的，而且還和我要的效果正好相反，多麻煩啊，所以大爺就直接反著搞，省時省力更省心，省省更健康，哦耶～
