Problem 639 Don't Get Rooked，擺城堡

此題給你一個 n 值，代表 n * n 的棋盤，接著輸入棋盤狀態，字元 '.' 代表甚麼都沒有，字元 'X' 代表牆。接下來，隨你怎麼擺西洋棋中的城堡，只要在合法狀態(只要城堡兩兩不互吃)下，輸出在此棋盤能擺最多城堡的數量。

此題要用到回溯演算法，只是要將棋盤狀態記錄下來，方便回溯。接著將此次城堡位置的一步路徑全部都禁止掉，但遇到字元 'X'(牆) 就要停止禁止。再接著找尋下一個城堡能擺入的位置。如此如此的執行下去，累計城堡數量，並將最大值記錄下來，最後印出。

一開始我們先讀入棋盤狀態，C 語言程式碼如下：

char Chess[5][5];  
for (i = 0; i < n; i ++)
    scanf("%s", Chess[i]);

接著寫一 visit 函式，使用上面解說的回溯法，C 語言程式碼如下：

void visit(char Chess[][5], int i, int j)
{
     int k, s, r;
     char cChess[5][5];
     for (k = 0; k < n; k ++) /* 紀錄此次棋盤所有狀態 */
         strcpy(cChess[k], Chess[k]);
     
     /* 擺入城堡並且將此城堡一步能到的路線全部禁止再擺入城堡 */   
     Chess[i][j] = 'P';
     perMax ++;
     for (k = i - 1; k >= 0 && Chess[k][j] != 'X'; k --)
         Chess[k][j] = 'P';
     for (k = i + 1; k < n && Chess[k][j] != 'X'; k ++)
         Chess[k][j] = 'P';    
     for (k = j - 1; k >= 0 && Chess[i][k] != 'X'; k --)
         Chess[i][k] = 'P';
     for (k = j + 1; k < n && Chess[i][k] != 'X'; k ++)
         Chess[i][k] = 'P';
         
     /* 找尋下一個城堡能擺入位置，並且再次呼叫  visit 函式 */    
     for (s = 0; s < n; s ++)
         for (r = 0; r < n; r ++)
         {
             if (Chess[s][r] == '.')
                 visit(Chess, s, r);
         }
    /* 記錄最大值 */         
    if (perMax > max)
        max = perMax;
        
     /* 回溯  */     
    for (k = 0; k < n; k ++)
         strcpy(Chess[k], cChess[k]);         
    perMax --; 
}

最後只需在主程式這樣呼叫並且印出：

max = 0;
for (i = 0; i < n; i ++)
    for (j = 0; j < n; j ++)
    {
        if (Chess[i][j] != 'X')
           visit(Chess, i, j);
    }
printf("%d\n", max);

By David.K

p639題目連結
回ACM題庫目錄
回首頁