a982 迷宮問題#1

解題想法

參考Naukri的做法，用BFS和Dijkstra走完整個迷宮，並印出(n-1,n-1)的值。

Step 1
先判斷每一格是障礙物還是空地，若為障礙物=-1、空地=9999。
Step 2
令起點為1、index為1(index在這裡用來當作步數)
Step 3
每走一步就遍歷整個map，先讓change=0，如果走到步數和index一樣的地，就看周圍(東西南北)是否有地可走，如果這塊地符合下列兩個條件，就把該地的步數更新。

1.這塊地還沒走過(=9999)
2.這塊地走過，但步數比index大。

Step 4
每次遍歷時，只要整個迷宮的資料有被更新過，change=1。在每次遍歷結束時都會檢查迷宮的資料是否有變動，沒有就代表無路可走，輸出no solution，有的話就繼續遍歷，直到(n-1,n-1)被更新為止。

AC (3ms, 128KB)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<stdio.h>
#include<string.h>

char s[102];
int map[102][102],max=9999;

int main(){
    int n,i,j,index=1;
    scanf("%d",&n);
    getchar();
    for(i=0;i<n;i++){
        scanf("%s",s);
        for(j=0;j<strlen(s);j++){
            if(s[j]=='#'){map[i][j]=-1;}
            else{map[i][j]=max;}
        }
    }
    if(map[n-2][n-2]==-1){printf("No solution!\n");return 0;}
    map[1][1]=1;
    while(map[n-2][n-2]==max){
        int change=0;
        for(i=1;i<=n-2;i++){
            for(j=1;j<=n-2;j++){
                if(map[i][j]==index){
                    if(map[i-1][j]>index){map[i-1][j]=index+1;change=1;}//N
                    if(map[i][j+1]>index){map[i][j+1]=index+1;change=1;}//E
                    if(map[i][j-1]>index){map[i][j-1]=index+1;change=1;}//W
                    if(map[i+1][j]>index){map[i+1][j]=index+1;change=1;}//S
                }
            }
        }
        if(!change){printf("No solution!\n");return 0;}
        index++;
    }
    printf("%d\n",map[n-2][n-2]);
    return 0;
}

封面圖源：Pinterest