發表新討論
#45381: 測試執行OK但送出只會輸出no solution


JengSwan (Jeng Swan)

a982. 迷宮問題#1 | From: [114.40.89.195] | 發表日期: 2025-02-22 16:21

程式碼：

#include <cstdio>
using namespace std;
int m = 10000;
char mp[101][101];
void solve(int n, int x, int y, int steps) {
    if (x == n - 2 && y == n - 2) {
        m = (steps < m ? steps : m);
        return;
    }
    if (x > 0 && mp[x-1][y] == '.') {
        mp[x-1][y] = '2';
        solve(n, x-1, y, steps + 1);
        mp[x-1][y] = '.';
    }
    if (x < n && mp[x+1][y] == '.') {
        mp[x+1][y] = '2';
        solve(n, x+1, y, steps + 1);
        mp[x+1][y] = '.';
    }
    if (y > 0 && mp[x][y-1] == '.') {
        mp[x][y-1] = '2';
        solve(n, x, y-1, steps + 1);
        mp[x][y-1] = '.';
    }
    if (y < n && mp[x][y+1] == '.') {
        mp[x][y+1] = '2';
        solve(n, x, y+1, steps + 1);
        mp[x][y+1] = '.';
    }
}
int main() {
    int n;
    scanf("%d", &n);

    char nl;
    scanf("%c", &nl);
    for (int i = 0 ; i < n ; i ++) {
        for (int j = 0 ; j < n ; j ++) {
            scanf("%c", &mp[i][j]);
        }
        scanf("%c", &nl);
    }
    if (mp[1][1] == '#') puts("11No solution!");
    else {
        solve(n, 1, 1, 1);
        if (m != 10000) printf("%d", m);
        else puts("No solution!");
    }
    return 0;
}

 

if (mp[1][1] == '#') puts("11No solution!"); 中的 11 是用來測試輸出的no solution的哪一種，結果發現都是跑完遞迴之後m還是10000造成，但測試執行沒有問題

畫面

請問為何會這樣？？

#45382: Re: 測試執行OK但送出只會輸出no solution


JengSwan (Jeng Swan)

a982. 迷宮問題#1 | From: [114.40.89.195] | 發表日期: 2025-02-22 19:18

程式碼：

#include
using namespace std;
int m = 10000;
char mp[101][101];
void solve(int n, int x, int y, int steps) {
    if (x == n - 2 && y == n - 2) {
        m = (steps < m ? steps : m);
        return;
    }
    if (x > 0 && mp[x-1][y] == '.') {
        mp[x-1][y] = '2';
        solve(n, x-1, y, steps + 1);
        mp[x-1][y] = '.';
    }
    if (x < n && mp[x+1][y] == '.') {
        mp[x+1][y] = '2';
        solve(n, x+1, y, steps + 1);
        mp[x+1][y] = '.';
    }
    if (y > 0 && mp[x][y-1] == '.') {
        mp[x][y-1] = '2';
        solve(n, x, y-1, steps + 1);
        mp[x][y-1] = '.';
    }
    if (y < n && mp[x][y+1] == '.') {
        mp[x][y+1] = '2';
        solve(n, x, y+1, steps + 1);
        mp[x][y+1] = '.';
    }
}
int main() {
    int n;
    scanf("%d", &n);

    char nl;
    scanf("%c", &nl);
    for (int i = 0 ; i < n ; i ++) {
        for (int j = 0 ; j < n ; j ++) {
            scanf("%c", &mp[i][j]);
        }
        scanf("%c", &nl);
    }
    if (mp[1][1] == '#') puts("11No solution!");
    else {
        solve(n, 1, 1, 1);
        if (m != 10000) printf("%d", m);
        else puts("No solution!");
    }
    return 0;
}

 

if (mp[1][1] == '#') puts("11No solution!"); 中的 11 是用來測試輸出的no solution的哪一種，結果發現都是跑完遞迴之後m還是10000造成，但測試執行沒有問題

畫面

請問為何會這樣？？


更新程式碼：

#include <iostream>
using namespace std;
int m = 10000;
char mp[101][101];
void solve(int n, int x, int y, int steps) {
    if (x == n - 2 && y == n - 2) {
        m = (steps < m ? steps : m);
        return;
    }
    if (x > 0 && mp[x-1][y] == '.') {
        mp[x-1][y] = '2';
        solve(n, x-1, y, steps + 1);
        mp[x-1][y] = '.';
    }
    if (x < n-1 && mp[x+1][y] == '.') {
        mp[x+1][y] = '2';
        solve(n, x+1, y, steps + 1);
        mp[x+1][y] = '.';
    }
    if (y > 0 && mp[x][y-1] == '.') {
        mp[x][y-1] = '2';
        solve(n, x, y-1, steps + 1);
        mp[x][y-1] = '.';
    }
    if (y < n-1 && mp[x][y+1] == '.') {
        mp[x][y+1] = '2';
        solve(n, x, y+1, steps + 1);
        mp[x][y+1] = '.';
    }
}
int main() {
    int n;
    scanf("%d", &n);

    char nl;
    scanf("%c", &nl);
    for (int i = 0 ; i < n ; i ++) {
        for (int j = 0 ; j < n ; j ++) {
            scanf("%c", &mp[i][j]);
        }
        scanf("%c", &nl);
    }
    if (mp[1][1] == '#') puts("11No solution!");
    else {
        mp[1][1] = '2';
        solve(n, 1, 1, 1);
        if (m != 10000) printf("%d", m);
        else puts("No solution!");
    }
    return 0;
}

結果同

#45383: Re: 測試執行OK但送出只會輸出no solution


leeguanhan0909@gmail.com (李冠翰)

a982. 迷宮問題#1 | From: [36.238.140.196] | 發表日期: 2025-02-22 21:17

程式碼：

#include
using namespace std;
int m = 10000;
char mp[101][101];
void solve(int n, int x, int y, int steps) {
    if (x == n - 2 && y == n - 2) {
        m = (steps < m ? steps : m);
        return;
    }
    if (x > 0 && mp[x-1][y] == '.') {
        mp[x-1][y] = '2';
        solve(n, x-1, y, steps + 1);
        mp[x-1][y] = '.';
    }
    if (x < n && mp[x+1][y] == '.') {
        mp[x+1][y] = '2';
        solve(n, x+1, y, steps + 1);
        mp[x+1][y] = '.';
    }
    if (y > 0 && mp[x][y-1] == '.') {
        mp[x][y-1] = '2';
        solve(n, x, y-1, steps + 1);
        mp[x][y-1] = '.';
    }
    if (y < n && mp[x][y+1] == '.') {
        mp[x][y+1] = '2';
        solve(n, x, y+1, steps + 1);
        mp[x][y+1] = '.';
    }
}
int main() {
    int n;
    scanf("%d", &n);

    char nl;
    scanf("%c", &nl);
    for (int i = 0 ; i < n ; i ++) {
        for (int j = 0 ; j < n ; j ++) {
            scanf("%c", &mp[i][j]);
        }
        scanf("%c", &nl);
    }
    if (mp[1][1] == '#') puts("11No solution!");
    else {
        solve(n, 1, 1, 1);
        if (m != 10000) printf("%d", m);
        else puts("No solution!");
    }
    return 0;
}

 

if (mp[1][1] == '#') puts("11No solution!"); 中的 11 是用來測試輸出的no solution的哪一種，結果發現都是跑完遞迴之後m還是10000造成，但測試執行沒有問題

畫面

請問為何會這樣？？


更新程式碼：

#include
using namespace std;
int m = 10000;
char mp[101][101];
void solve(int n, int x, int y, int steps) {
    if (x == n - 2 && y == n - 2) {
        m = (steps < m ? steps : m);
        return;
    }
    if (x > 0 && mp[x-1][y] == '.') {
        mp[x-1][y] = '2';
        solve(n, x-1, y, steps + 1);
        mp[x-1][y] = '.';
    }
    if (x < n-1 && mp[x+1][y] == '.') {
        mp[x+1][y] = '2';
        solve(n, x+1, y, steps + 1);
        mp[x+1][y] = '.';
    }
    if (y > 0 && mp[x][y-1] == '.') {
        mp[x][y-1] = '2';
        solve(n, x, y-1, steps + 1);
        mp[x][y-1] = '.';
    }
    if (y < n-1 && mp[x][y+1] == '.') {
        mp[x][y+1] = '2';
        solve(n, x, y+1, steps + 1);
        mp[x][y+1] = '.';
    }
}
int main() {
    int n;
    scanf("%d", &n);

    char nl;
    scanf("%c", &nl);
    for (int i = 0 ; i < n ; i ++) {
        for (int j = 0 ; j < n ; j ++) {
            scanf("%c", &mp[i][j]);
        }
        scanf("%c", &nl);
    }
    if (mp[1][1] == '#') puts("11No solution!");
    else {
        mp[1][1] = '2';
        solve(n, 1, 1, 1);
        if (m != 10000) printf("%d", m);
        else puts("No solution!");
    }
    return 0;
}

結果同

本題用DFS應該很難AC，不過我把scanf改成cin可以到75%(#3TLE(1s))
建議使用BFS，下面的測資直接說明為何此題使用BFS而非DFS

9
#########
#.......#
#.......#
#.......#
#.......#
#.......#
#.......#
#.......#
#########

在每一格的上下左右幾乎都可以走時，DFS會花費許多時間在尋找非最佳解上，BFS則不會。

雖然偵測到步數>=m時直接return，但只要n>20依然TLE(1s)。

改過後程式

順帶一提，上述測資是用python生的，a982生成極端測資

ZeroJudge Forum