hdu 1026 Ignatius and the Princess I - c++编程基础

我指出了上面提到的问题，更本不可能更新最小时间。因为按照上面的写法，终点只可能入队和出队一次。
然后我又准备用最短路的思想模拟，但是还是准备在上面的基础上改一下，于是每一个点出队我也标记了下，这样保证了终点可以多次遍历到
但是这样一来就无法解决跳出 BFS 问题，于是我想到每一个点最多被上下左右的点走一次，那么是不是标记每一个点最多入队四次就可以了呢？
样例同样出来了，结果还是 WA 。。。
想了下：可能是我虽然标记了入队四次，但是可能这四次都是由同一个点到达的，那么也和标记一次没有分别了，还是无法解决上面的更新最短时间问题。

所以：最终还是只能按照最短路的思想遍历。

很裸的题目了，本来只是打算练下手，结果还是做了很久。菜鸟要努力 Fighting ！！！Come on

code：

#include
#include
#include
#include
#include
using namespace std;

const int maxn = 110;
const int INF = maxn*maxn*10;

int map[maxn][maxn]; //记录图
int vis[maxn][maxn]; //标记入队
char str[maxn];
int n,m;

int dir[4][2] = {0,1, 0,-1, -1,0, 1,0};

//定义优先队列：对于入队了的点,先出队的是时间少的,那么第一个到达终点的就是结果
struct Node{
    int x,y; //当前到达的点
    int time; //耗费的时间

    bool operator < (const Node &b) const{
        return b.time < time;
    }
};

//每一个点的前驱, 由于是逆向搜索的, 所以记录的其实是当前点的下一个点了
struct Pre{
    int px, py;
}pre[maxn][maxn];

void bfs()
{
    Node now, next;
    priority_queue q;
    while(!q.empty()) q.pop();

    now.x = n; now.y = m; //从终点走向起点
    now.time = map[n][m]; //注意：终点也可能会有怪兽
    pre[n][m].px = -1; //输出边界
    q.push(now);

    memset(vis, 0, sizeof(vis)); //为方便快速输出路径, 从终点往起点找
    vis[n][m] = 1; //标记终点入队

    while(!q.empty())
    {
        now = q.top(); q.pop();

        if(now.x == 1 && now.y == 1) //一旦到达起点
        {
            printf("It takes %d seconds to reach the target position, let me show you the way.\n", now.time);
            int time = 1;
            int x = now.x, y = now.y; //当前的位置
            int nx = pre[x][y].px, ny = pre[x][y].py; //下一个位置
            while(pre[x][y].px != -1) //不停的找前驱
            {
                printf("%ds:(%d,%d)->(%d,%d)\n", time++, x-1, y-1, nx-1, ny-1);
                while(map[nx][ny]--) //如果有怪兽
                {
                    printf("%ds:FIGHT AT (%d,%d)\n", time++, nx-1, ny-1);
                }
                x = nx; y = ny; //继续查找下一个点
                nx = pre[x][y].px, ny = pre[x][y].py;
            }
            printf("FINISH\n");
            return; //结束
        }

        for(int i = 0; i < 4; i++)
        {
            next.x = now.x+dir[i][0];
            next.y = now.y+dir[i][1];

            if(map[next.x][next.y] >= 0 && !vis[next.x][next.y]) //当前点可以走,并且没有入队过
            {
                vis[next.x][next.y] = 1; //标记入队

                next.time = now.time + 1 + map[next.x][next.y];
                pre[next.x][next.y].px = now.x; //前驱记录
                pre[next.x][next.y].py = now.y;

                q.push(next);
            }
        }
    }

    printf("God please help our poor hero.\n"); //不能到达
    printf("FINISH\n");
    return;
}

int main()
{
    while(scanf("%d%d", &n,&m) != EOF)
    {
        gets(str);
        for(int i = 0; i <= n+1; i++) //周围加边
            for(int j = 0; j <= m+1; j++)
                map[i][j] = -1;

        char c;
        for(int i = 1; i <= n; i++) //输出的时候注意 -1 处理下
        {
            for(int j = 1; j <= m; j++)
            {
                scanf("%c", &c);
                if(c != 'X')
                {
                    if(c == '.') map[i][j] = 0;
                    else map[i][j] = c-'0';
                }
            }
            gets(str);
        }

        bfs();
    }
    return 0;
}

hdu 1026 Ignatius and the Princess I(三)