Description

輸入 3x3 二維陣列代表地圖，其中包含 1 和 M 以及 0，例如

1 0 0

0 0 0

M 0 0

 

從數字 1 的位置開始走，只能往右下左上(R,D,L,U)四個方向移動，目標是要走過M個位置，而且每個位置只能走過一次，直到走到 M 為止

你的程式要輸出YES / NO，代表 1 是否能夠走到 M

 

hint:

1. 可以把 map 開大一點，int map[5][5]; 但是最好是先把內容填成 -1，讓外緣一圈邊界的值都是 -1，這樣可以區別 0 和 -1。此外走過之後的位置也要填上適當的整數值。

2. 建議可以嘗試隨機的方法，概念如下：

從 1 的位置開始，隨機選擇 4 個方向中任一個，如果可以走，就移到新的位置，並且在地圖上將該位置標記為 2，

然後繼續進行同樣的隨機動作，找尋可以標為 3 的位置。如果隨機選定的方向不能走 (超出地圖或是已經走過)，

就在原來的位置重新再隨機挑選方向。

假如上述的隨機嘗試經過 10 次之後都失敗 (移動不了)，就將全部的狀態還原，回到 1 的位置重新開始。

假如從 1 開始走，走到失敗之後重設為原始狀態，這樣的情況經歷了一百萬次還是走不到 M，就讓程式結束並且輸出 No.

 

底下是模擬丟骰子的程式碼：

#include 
#include 
int main(void)
{
    int i, x;
    for (i=0; i<100; i++) {
        x = rand()%6 + 1;
        printf("%3d", x);
    }
    return 0;
}

 

Input

N

M₁

地圖₁

M₂

地圖₂

...

M_N

地圖_N

 

N代表有幾組地圖

1 < M_i < 10, for i=1, 2, ..., N

Output

YES / NO

YES / NO

...

YES / NO

 

總共有N筆答案

每筆答案的後面請加上換行

並注意字母全部為大寫

Sample Input  Download

Sample Output  Download

Tags

Discuss