HDU 1010 Tempter of the Bone

读题\(→\)\(BFS\)裸题，信心满满交了一发\(→\)\(\color{red}{WrongAnswer}\)

const int N=10;
char g[N][N];
int dist[N][N];
int n,m,tim;
PII st,ed;

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

int bfs()
{
    memset(dist,-1,sizeof dist);
    queue<PII> q;
    q.push(st);
    dist[st.fi][st.se]=0;

    while(q.size())
    {
        PII t=q.front();
        q.pop();

        if(t == ed) return dist[t.fi][t.se];

        for(int i=0;i<4;i++)
        {
            int a=t.fi+dx[i],b=t.se+dy[i];
            if(!check(a,b) || g[a][b] == 'X') continue;
            if(dist[a][b] == -1)
            {
                dist[a][b]=dist[t.fi][t.se]+1;
                q.push({a,b});
            }
        }
    }
    return -1;
}

int main()
{
    while(~scanf("%d%d%d",&n,&m,&tim))
    {
        if(!n && !m && !tim) break;

        for(int i=0;i<n;i++) scanf("%s",&g[i]);

        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
            {
                if(g[i][j] == 'S') st={i,j};
                if(g[i][j] == 'D') ed={i,j};
            }

        int t=bfs();
        if(t == tim) puts("YES");
        else puts("NO");
    }
    //system("pause");
}

错因分析：
本题要求时间刚好是\(t\)到达终点，只需经过的街区不可以重复即可

所以本题不能用\(BFS\)，\(BFS\)得到的是最短路径，而此题的路径不一定最短。

于是乎，改成可行性\(DFS\)+回溯\(→\color{green}{Accepted}\)

const int N=10;
char g[N][N];
bool vis[N][N];
int n,m,tim;
PII st,ed;

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

bool dfs(int x,int y,int t)
{
    if(g[x][y] == 'D')
    {
        if(t == tim) return true;
        return false;
    }

    for(int i=0;i<4;i++)
    {
        int a=x+dx[i],b=y+dy[i];
        if(!check(a,b) || g[a][b] == 'X') continue;
        if(!vis[a][b])
        {
            vis[a][b]=true;
            if(dfs(a,b,t+1)) return true;
            vis[a][b]=false;
        }
    }
    return false;
}

int main()
{
    while(~scanf("%d%d%d",&n,&m,&tim))
    {
        if(!n && !m && !tim) break;

        memset(vis,0,sizeof vis);

        for(int i=0;i<n;i++) scanf("%s",&g[i]);

        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
            {
                if(g[i][j] == 'S') st={i,j};
                if(g[i][j] == 'D') ed={i,j};
            }

        vis[st.fi][st.se]=true;
        bool ok=dfs(st.fi,st.se,0);
        if(ok) puts("YES");
        else puts("NO");
    }
    //system("pause");
}