發表新討論
#45151: 用DFS解結果發現會TLE就順便丟上來了


kingdom0987123@gmail.com (Alex Cheng)

學校 : 不指定學校
編號 : 196345
來源 : [140.117.194.238]
最後登入時間 ：
2024-10-06 02:13:07
a982. 迷宮問題#1 | From: [118.233.2.202] | 發表日期 : 2025-01-15 18:42

先說我也是小白, code可能寫的不是很好, 有興趣的可以把以下註解的code還原、34行設中斷點, 在除錯模式觀察dfs怎麼走迷宮 :

// 迷宮問題1 //

// start from (1, 1).
// try to travel four directions,
// if there is a passage, then record now positon and go to next position.
// record lenth, when arrive at endpoint, compare it with minLenth.

#include <stdio.h>

char maze[100][100], trail[10000][2];
int n, minLen, destX, destY, visited[100][100] = {0};

void ShowNowPos(int x, int y)
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (i == x && j == y)
                printf("@ ");
            else
                printf("%c ", maze[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}

void DFS(int nowX, int nowY, int len)
{
    if (maze[nowX][nowY] == '#' || visited[nowX][nowY] == 1)
        return;
   
    // ShowNowPos(nowX, nowY);

    if (nowX == destX && nowY == destY)
    {
        if (len < minLen)
            minLen = len;

        return;
    }

    // maze[nowX][nowY] = 'v';
    visited[nowX][nowY] = 1;

    BFS(nowX + 1, nowY, len + 1);  // down
    BFS(nowX, nowY + 1, len + 1);  // right
    BFS(nowX - 1, nowY, len + 1);  // up
    BFS(nowX, nowY - 1, len + 1);  // left

    // maze[nowX][nowY] = '.';
    visited[nowX][nowY] = 0;
}

int main()
{
    scanf("%d", &n);

    destX = n - 2;
    destY = n - 2;
    minLen = n * n;

    for (int i = 0; i < n; i++)
    {
        scanf("%s", maze[i]);
    }

    BFS(1, 1, 1);

    if (minLen == n * n)
        printf("No solution!");
    else
        printf("%d", minLen);

    return 0;
}
 
ZeroJudge Forum