HDU--杭电--1026--Ignatius and the Princess I--广搜--直接暴力0MS，优先队列的一边站

别人都是广搜+优先队列，我没空临时学，所以就直接自己暴力了
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); //把入队的坐标处理好并入队
     &nbs

补充：软件开发 , C++ ,