7-3 解答

• 一開始全部地方都是沒走過
• 若「超出邊界」或「走過了」或「是x」，就停止
• 注意使用陣列時不可以超出範圍
• 往上下左右亂走，走過要標記已走過
• 遇到 O 就記錄下來

#include<iostream>
using namespace std;

int max_x, max_y;       //地圖長寬
char maze[105][105];    //地圖
bool visited[105][105]; //visited是紀錄已經拜訪過的格子
bool isCookieFound;     //紀錄這次老鼠能不能成功找到餅乾

void run( int y, int x )
{
    //TODO ↓

    //如果 碰到上下左右邊界的話，就回頭   

    //如果 已經拜訪過這格 或 這一格是障礙物 的話，就回頭

    //標記此格已拜訪過

    //如果這一格是餅乾，答案就確定是"Yes"

    //run( y-1, x ); -> 另外還有3個該怎麼run呢?
}

int main()
{
   //start_x,start_y 一開始就是老鼠所在的位置
   int start_x, start_y;
   while( cin >> max_x >> max_y )
   {
       //TODO ↓

       //依序輸入每個格子的資訊

       //將拜訪過的清單整個初始化為false

       //如果這一格剛好是老鼠，那就代表isCookieFound要設為true，代表找到餅乾

       //初始化isCookieFound為false，代表一開始還沒找到餅乾

       run( start_y, start_x );

       //用isCookieFound來判斷最後是否成功


   }
   return 0;
}

解答

#include<iostream>
using namespace std;

int max_x, max_y;      //地圖的邊界
char maze[105][105];
bool visited[105][105];//紀錄地圖的格子是否有被拜訪過，true代表拜訪過，false則是未拜訪
bool isCookieFound;    //是否有找到餅乾

void run( int y, int x )
{
    //如果 '超出上下左右的邊界' 或 '已經找到餅乾了' 就return
    if( x < 0 || x >= max_x || y < 0 || y >= max_y || isCookieFound )
        return;

    //如果 '已經拜訪過這格' 或 '這一格是障礙物' 就return
    if( visited[y][x] == true || maze[y][x] == 'x' )
        return;

    //拜訪了此格，visited[y][x]=true代表拜訪過，false則是未拜訪過
    visited[y][x] = true;

    //如果這一格剛好是餅乾，則記錄找到餅乾
    if( maze[y][x] == 'O' )
        isCookieFound = true;

    run( y-1, x ); //往上方探索 ↑
    run( y+1, x ); //往下方探索 ↓
    run( y, x-1 ); //往左方探索 ←
    run( y, x+1 ); //往右方探索 →

}

int main()
{
   int i, j, start_x, start_y;
   while( cin >> max_x >> max_y )
   {
      for( i = 0 ; i < max_y ; i++ )
        for( j = 0 ; j < max_x ; j++ )
        {
           cin >> maze[i][j]; //輸入此格地圖資訊，可能是 M , O , . , x
           visited[i][j] = false; //初始化，讓每一個格子都是未拜訪過的
           if( maze[i][j] == 'M' ) //如果輸入的 M 小鼠
           {
              //紀錄座標，方便等等從小鼠的位置開始搜尋
              start_y = i;
              start_x = j;
           }
        }

      isCookieFound = false;
      run( start_y, start_x ); //從小鼠的位置開始進行DFS搜尋

      if( isCookieFound ) //isCookieFound為true 代表有找到餅乾
        cout << "Yes!" << endl;
      else
        cout << "Oh, no!" << endl;
   }
   return 0;
}