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題庫目錄
回首頁

Problem 825 Walking on the Safe Side，走最省的路

其實一看圖就知道，題目會給你橫縱各有幾條路，再給你幾個中斷點，問你有幾條最省的路從左上角到右下角。所以我們可以建立陣列，可以走的路訂為 0，不可走的路訂為 1。C 語言程式碼如下：

char str[200], *pch;
int road[101][101];
int i, j, k;
scanf("%d %d", &W, &N);
getchar();
memset(road, 0, sizeof(road));

for (i = 0; i < W; i ++)
{
    gets(str);
    pch = strtok(str, " ");
    sscanf(pch, "%d", &j);
    pch = strtok(NULL, " ");
    while (pch != NULL)
    {
        sscanf(pch, "%d", &k);
        pch = strtok(NULL, " ");
        road[j - 1][k - 1] = 1;
    } 
}

再來，用回溯演算法寫一函式讓它去嘗試每一條可以走的路，最省的路只能走右或走下，所以只需要嘗試這兩條路即可。C 語言程式碼如下：

void visit(int road[][101], int i, int j)
{
    road[i][j] = 1;
    
    if (i == W - 1 && j == N - 1) count ++;
    
    if (road[i][j + 1] == 0 && j < N) visit(road, i, j + 1);
    if (road[i + 1][j] == 0 && i < W) visit(road, i + 1, j);    
    
    road[i][j] = 0;
}

最後，只須再主程式呼叫函式並且印出：

visit(road, 0, 0);
printf("%d\n", count);

By David.K

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

Problem 300 Maya Calendar，日歷的轉換

馬雅文化使用兩種日歷格式。

第一種稱為 Haab 的日歷格式，一年有 365 天，但卻有 19 個月份，而 19 個月份的名稱依序為 pop, no, zip, zotz, tzec, xul, yoxkin, mol, chen, yax, zac, ceh, mac, kankin, muan, pax, koyab, cumhu, uayet，頭 18 個月份每個月有 20 天，而天數由 0 到 19 計算，最後一個月只有 5 天，一共 365 天。

第二種稱為 Tzolkin 的日歷格式，一年有 260 天，由 imix, ik, akbal, kan, chicchan, cimi, manik, lamat, muluk, ok, chuen, eb, ben, ix, mem, cib, caban, eznab, canac, ahau 共 20 個名稱與 13 個數字循環而成，就如同我們的文化使用天干地支，例如：甲子、乙丑、丙寅...等等。也就是說我們列出前 20 天的循環會是：1 imix, 2 ik, 3 akbal, 4 kan, 5 chicchan, 6 cimi, 7 manik, 8 lamat, 9 muluk, 10 ok, 11 chuen, 12 eb, 13 ben, 1 ix, 2 mem, 3 cib, 4 caban, 5 eznab, 6 canac, 7 ahau。

題目要求，輸入第一種日歷格式要轉換為第二種日歷格式。

這題其實只要把輸入的格式轉換為天數，再去求第二種日歷格式會是多少就可以了。

By David.K

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