Question

杭电acm第1026题，我用dijkstra算法，测试了不少数据都行，怎么还是WA呀? 有什么需要注意的地方吗?

Answer 1

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;

#define MK(a,b) make_pair((a),(b))
#define PII pair<int,int>
const int N = 110;
const int dir[2][4] = {{1,-1,0,0},{0,0,1,-1}};
int n, m;
char mtx[N][N];
int stp[N][N], pre[N][N] = {{-1}};

bool check(int x, int y)
{
    return x >= 0 && x < n && y >= 0 && y < m;
}

void dfs(int x, int y, int c)
{
    if (!c) return;
    int prex = x - dir[0][pre[x][y]], prey = y - dir[1][pre[x][y]];
    dfs(prex, prey, c - mtx[x][y]);
    int t = c - mtx[x][y] + 1;
    printf("%ds:(%d,%d)->(%d,%d)\n",t,prex,prey,x,y);
    for (int i = 1;i<mtx[x][y];i++)
    {
        printf("%ds:FIGHT AT (%d,%d)\n",t + i, x, y);
    }
}

int main()
{
//    freopen("a.txt","r",stdin);
    while(scanf("%d%d",&n,&m) == 2)
    {
        for (int i = 0;i<n;i++)
        {
            scanf(" %s",mtx[i]);
            for (int j = 0;j<m;j++)
            {
                if (mtx[i][j] == '.')
                    mtx[i][j] = 1;
                else if (mtx[i][j] != 'X')
                    mtx[i][j] -= '0' - 1;
            }
        }
        memset(stp, 0x3f, sizeof stp);
        queue<PII > Q;
        Q.push(MK(0,0));
        stp[0][0] = 0;
        while(!Q.empty())
        {
            PII cur = Q.front();
            int x = cur.first, y = cur.second;
            Q.pop();
            for (int i = 0;i<4;i++)
            {
                int curx = x + dir[0][i];
                int cury = y + dir[1][i];
                if (check(curx, cury) && mtx[curx][cury] != 'X')
                {
                    if (stp[curx][cury]>stp[x][y] + mtx[curx][cury])
                    {
                        stp[curx][cury]=stp[x][y] + mtx[curx][cury];
                        pre[curx][cury]=i;
                        Q.push(MK(curx, cury));
                    }
                }
            }
        }
        if (stp[n - 1][m - 1] != 0x3f3f3f3f)
        {
            printf("It takes %d seconds to reach the target position, let me show you the way.\n",stp[n - 1][m - 1]);
            dfs(n - 1,m - 1,stp[n - 1][m - 1]);
        }
        else
        {
            puts("God please help our poor hero.");
        }
        puts("FINISH");
    }
    return 0;
}

楼主我直接用队列BFS的过的，没觉得有什么坑，我只是栽在了这组数据

2 2

.9

X.

就是起点重点旁边就是一个怪兽的数据。

其他地方没什么要注意的。

楼主可能是代码有细节错误吧？而且有可能数组开得不够大？或者输出的英文因为是手打的，有错误吧？不知道楼主的代码还真难说那里有问题