qq_52187065
qq_52187065
采纳率100%
2021-02-09 15:37

DFS只搜了一条路 求大佬解答

已采纳
#include<stdio.h>
char map[30][30];
int vis[30][30] = { 0 };
int m, n, i, j;
int ans = 1000;
int step = 0;
int t[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };

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

void dfs(int x, int y,int step)
{
    vis[x][y] = 1;   
    if (step > ans)
        return;
    if (map[x][y] == '*')
    {
        ans = step;
        return;
    }
    for (i = 0; i < 4; ++i)
    {         
        int newx = x + t[i][0];
        int newy = y + t[i][1];
        if (!vis[newx][newy] && map[newx][newy] != '#' && in(newx, newy))
            dfs(newx, newy, step + 1);        
    }    
    vis[x][y] = 0;
}

int main()
{
    scanf("%d%d", &m, &n);
    for (i = 0; i < m; i++)
    {
        scanf("%s", map[i]);
    }
    for (i = 0; i < m; i++)
    {
        for (j = 0; j < n; j++)
        {
            if (map[i][j] == '@')
                dfs(i, j, 0);
        }
    }
    printf("%d", ans);
    return 0;
}
  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享
  • 邀请回答

1条回答

  • yueyuedog 蒟蒻一枚 2月前

    不要定义全局变量step,和参数的step名字一样,用的时候一直用的是全局变量的step,所以全局变量step的值始终是0,步数不会增加。

    点赞 评论 复制链接分享

为你推荐