演算法筆記 - Robot路徑全展開

第一篇文章!

到大陸上班之後發現沒辦法存取大部份的網路資源....所以想找個地方來放自己的筆記.
終極目標是希望在大陸工作的時候也可以輕易的存取,
不過看起來好像只有CSDN可以比較簡單做到....
就先放在Blogger暫存一下好了 XD

這是上禮拜跟Jay哥拿了一本演算法的題庫的其中一題:

[題目]
掃地機器人可以進行上下左右的任意移動, 每次移動一格, 且不能走到重複的格子

當移動 1 次的時候, 總共會有 4 種移動結果
( ↑ / ↓ / ← / → )

當移動 2 次的時候, 總共會有 12 種移動結果
(↑↑ / ↑← / ↑→ ) * 4

當移動 3 次的時候, 總共會有 36 種移動結果
{(↑↑↑ / ↑↑← / ↑↑→ ) + (↑←← / ↑←↑ / ↑←↓) + (↑→→ / ↑→↑ / ↑→↓)} * 4

問題來了,

當移動了 13 次的時候, 總共會有幾種可能性?

[想法紀錄]
1.) 我可以固定起始方向, 之後將該計算結果*4就是答案
2.) 我需要記錄機器人走過的座標, 這樣才知道是否有走到重複的路徑上
3.) 或者....機器人的每一步都是自由的, 我應該讓他每一步都可以自由的進行上下左右移動,
再將不能移動到的位置幹掉.

羅列出來的想法大概就如上述這樣,
那麼接下來把需要的元素都展開來看看

[實作想法]
1.) 我需要紀錄座標, 那麼是不是需要一個二維Array?
2.) 我需要紀錄當前機器人所在的位置,
     並且我想要初始化它的座標點到(0, 0)去, 那麼長寬最好是一個奇數.
3.) 我可能需要傳遞這個二維Array進去函數內進行運算,
     而我們需要知道二維函數的傳遞形式並不是pointer to pointer:

int test[5][10];

void wrongFunc(int **array);
wrongFunc(&test[0]);

/* array 變數本身可以 decay 成記憶體起頭的位置,
    所以你要描述的是一個 array 的 pointer, 長度為10,
    並且這個 pointer 的 array 成員會再分別指向各自的一維 array
*/

void rightFunc(int (*array)[10]); // array 是一個 pointer, 它指向 int [10]
rightFunc(test);
rightFunc(&test[0]); //這兩個敘述式等價

4.) 我可以先展開寬度, 或者先展開深度.
展開寬度一般是會搭配權重, 進行縮減 (像是 Beam Search 這種演算)
但由於要做的是全路徑展開, 所以我應該可以用遞迴搭配深度展開來完成

[開始實作]
我需要的元素有這些:
1.) 整個走過的點 (map[50][50])
2.) 目前的座標 (x, y)
3.) 目前的深度 (depth)

Pseudo code大概長這樣:

boolean freeRun( map, x, y, depth, target) {
    if (depth == target) {
        return true;
    } else {
        for (way = 0; way < 4; way++) {
            switch (way) {
               case 0:
                  x++;
                  break;
               ...
               case 3:
                  y--;
                  break;
            }
            depth++;
            if (map[x][y] == 1) {return false;} // hit end
            else {
                map[x][y] = 1;
                boolean result = freeRun(map, x, y, depth);
                if (result != true) {
                    reset(map, x, y, depth);
                    continue;
                }
            }
        }
    }
    // Should never come here
    return false;
}

我要傳入陣列, 座標, 有時候還得Reset它們!?
是否有點太麻煩?
=> 使用Structure, 這樣我就不用管到底要怎麼傳陣列了 +_+

想複製, 那就直接傳Structure
想改值, 那就傳入&Structure
太美妙惹~~~

那麼就定義一個Structure吧~

#define COLUME_SIZE (50)
#define ROW_SIZE (50)
typedef struct Map {
 int pos[ROW_SIZE][COLUME_SIZE];
 int x;
 int y;
} Map;

把採點另外放到subFunction, 並加入debug log

void recordMap(Map *map) {
 int x = map->x;
 int y = map->y;
 map->pos[x][y] = 1;
 if (bDebug) printf("\t***record map[%d][%d] = %d\n", x-25, y-25, map->pos[x][y]);
}

最後改寫freeRun函式跟main函式, 完成~

int finalCnt = 0;
int bDebug = 0;

int main(int argc, char** argv) {
 int steps = 0;
 cout << "Steps to go: ";
 cin >> steps;
 cout << "Calculating for " << steps << " steps." << endl;

 getSteps(steps);
}

int getSteps(int step) {
 Map map;
 memset(&map, 0, sizeof(map));

 // Start from (25, 25)
 map.x = 25;
 map.y = 25;
 recordMap(&map);
 step--;

 // Running
 // - Consider only 1 ways when start running, then multiple as 4 will be the answer
 map.y++;
 recordMap(&map);
 step--;

 cout << "Ready to free run..." << endl;
 // - Free run
 freeRun(map, step);

 cout << "finalCnt = " << finalCnt*4 << endl;
}

void freeRun(Map map, int step) {
 int i = 0;

 // Backup the current step
 Map tempMap = map;

 if (bDebug) printf("+++========================================\n");
 for (i = 0; i < 4; i++) {
  if (bDebug) printf("\nfreeRun - step %d at [%d][%d]\n", step, tempMap.x - 25, tempMap.y - 25);
  switch (i) {
   case 0:
    // x+
    map.x++;
    break;
   case 1:
    // x-
    map.x--;
    break;
   case 2:
    // y+
    map.y++;
    break;
   case 3:
    // y-
    map.y--;
    break;
  }

  if (bDebug) printf("\t (i: %d) [%d][%d] => [%d][%d]\n", i, tempMap.x-25, tempMap.y-25, map.x-25, map.y-25);
  step--;

  if (map.pos[map.x][map.y] == 1) {
   // Dead end, go next try
   if (bDebug) printf("\t\tDead end: map[%d][%d] is 1\n", map.x-25, map.y-25);
  } else {
   recordMap(&map);
   if (step == 0) {
    finalCnt++;
    if (bDebug) printf("Meet final count at map[%d][%d]...%d\n\n", map.x-25, map.y-25, finalCnt);
    // Dead end, go next try
   } else {
    // Deep first, go next layer
    freeRun(map, step);
   }
  }

  // Recover for this turn running;
  step++;
  map = tempMap;

 }
 if (bDebug) printf("===========================================\n");
}