Problem 10026 Shoemaker's Problem，工作排序

本來我打算放棄解這題，不過 google 了一下，發現只須要用到排序，就能解決這一題。

假設有兩個工作要比較，d1, m1 和 d2, m2 (d 為工作天，m 為延遲罰金)，要比較它們的大小就讓它們工作天以及延遲罰金互乘，再去比較大小，則可很輕易的就排序出結果，例如： 3個工作天，延遲罰金 5 以及 4 個工作天，延遲罰金 7，而 3 * 7 > 4 * 5，則後者排序在前，前者排序在後。

關鍵程式碼如下：

#define SIZE 1001
struct Job
{
    int num;
    int wDay;
    int dMoney;
};
struct Job job[SIZE], r;

主程式內 ...

scanf("%d", &m);
for (i = 0; i < m; i ++)
{
    scanf("%d %d", &day ,&money);
    job[i].wDay = day, job[i].dMoney = money;
    job[i].num = i + 1;
    for (j = i; j >= 1; j --)
    {
        if (job[j].wDay * job[j - 1].dMoney < 
            job[j - 1].wDay * job[j].dMoney)
        {
            r = job[j], job[j] = job[j - 1],
            job[j - 1] = r;
        }
        else break;
    }
}

最後只要逐個印出 job 陣列內的 num 值就好了。

By David.K

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

Problem 10048 Audiophobia，噪音恐懼症

此題與 Problem 534 Frogger 用的方法一模一樣，只是這題更簡單了，因為它不需要算點與點之間的距離，它直接給你某路口走到某路口所經過的街道，噪音有多少分貝。

因為這一題有些地方不能直達，所以值還會是 0，所以我初始化就全部給他定 1000，噪音到 1000 分貝，耳膜也破了吧。再接著用最小路徑演算法，答案就會呼之欲出了。

for (i = 1; i <= C; i ++)
    for (j = 1; j <= C; j ++)
        W[i][j] = 1000;

for (i = 0; i < S; i ++)
{
    int noise, p1, p2;
    scanf("%d %d %d", &p1, &p2, &noise);
    W[p1][p2] = W[p2][p1] = noise;
}
for (k = 1; k <= C; k ++)
    for (i = 1; i <= C; i ++)
        for (j = 1; j <= C; j ++)
            if (i != j)
                W[i][j] = min(W[i][j], max(W[i][k], W[k][j]));
if (caseNum != 1) printf("\n");
printf("Case #%d\n", caseNum ++);
for (i = 1; i <= Q; i ++)
{
    int p1, p2;
    scanf("%d %d", &p1, &p2);
    int minNoise = W[p1][p2];
    if (minNoise != 1000) printf("%d\n", W[p1][p2]);
    else printf("no path\n");
}

By David.K

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

Problem 10015 Joseph's Cousin，吃人遊戲

此題為紐西蘭停電的進階版，因為他不是從頭到尾數同一個數，而是要吃掉第 i 個人，就要數第 i 個質數，直到吃剩最後一個人才停，要輸出這最後一個人在什麼位置。

我用的方法很粗糙，暴力破解，所以執行時間有點長，不過還是過了。

首先建立質數表，數值到 33000，就能把前 3502 的質數找出來：

#define SIZE 33000
int prime[SIZE + 1];
int prime_table[SIZE], prime_table_len = 0;

void makeprime(){
    int i, j;
    prime_table[prime_table_len ++] = 2;
    for(i = 3; i < SIZE; i += 2)
        if(!prime[i]){
            for(j = i + i; j <= SIZE; j += i)
                prime[j] = 1;
            prime_table[prime_table_len ++] = i;
        }
}

再用暴力破解即可，C 語言程式碼如下：

int nextLife(int isLife[], int site, int n)
{
    while (!isLife[site])
    {
        site ++;  
        if (site >= n) site -= n;
    }
    return site;
}

int main()
{
    makeprime();
    int n, i, j, life;
    while (scanf("%d", &n) == 1 && n)
    {
        int isLife[n], nowSite = 0, count;
        for (i = 0; i < n; i ++) /* 初始化 */
            isLife[i] = 1;
        for (i = 0; i < n - 1; i ++)
        {
            count = prime_table[i] - 1;
            
            for (j = 0; j < count; j ++)
            {
                nowSite = nextLife(isLife, nowSite, n);
                nowSite ++;
                if (nowSite >= n) nowSite -= n;
            }
            nowSite = nextLife(isLife, nowSite, n);
            isLife[nowSite] = 0;
        }
        for (i = 0; i < n; i ++)
            if (isLife[i]) { printf("%d\n", i + 1); break; }
        
    }
    return 0;
}

By David.K

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

Problem 10010 Where's Waldorf?，找字串

給你一雜亂無章的字元陣列，要你從這字元陣列中，找尋出一些相符字串。只是搜尋字串必須朝著某一方向進行，例如：
要找尋底下四個字串
Waldorf
Bambi
Betty
Dagbert
而在底下陣列出現之位置如變色所在：

abcDEFGhigg
hEbkWalDork
FtyAwaldORm
FtsimrLqsrc
byoArBeDeyv
Klcbqwikomk
strEBGadhrb
yUiqlxcnBjf

上面例子已經很清楚的顯示，搜尋字串必須朝某一方向，不能彎來彎去，而輸出要輸出字串符合的開頭位置：
2 5
2 3
1 2
7 8

此題要用遞迴來解決，但是一旦決定方向，便不再改變。寫一函式嘗試核對字串，傳入陣列位置 i, j，以及找尋字串目前索引 index 和方向的編號 id(此數決定該往何方向核對字串)，C 語言程式碼如下：

#define SIZE 51

char W[SIZE][SIZE];
char str[200];
int row, col, isFind, len;

void searchStr(int i, int j, int index, int id)
{ 
    if (W[i][j] != str[index]) return;
    if (isFind || index == len - 1) {isFind = 1; return;}
    else
    {
        /* 左 */
        if (j - 1 >= 0 && (!id || id == 1)) 
            searchStr(i, j - 1, index + 1, 1);
        /* 左上 */
        if (j - 1 >= 0 && i - 1 >= 0 && (!id || id == 2)) 
            searchStr(i - 1, j - 1, index + 1, 2);
        /* 上 */
        if (i - 1 >= 0 && (!id || id == 3)) 
            searchStr(i - 1, j, index + 1, 3);
        /* 右上 */
        if (j + 1 < col && i - 1 >= 0 && (!id || id == 4)) 
            searchStr(i - 1, j + 1, index + 1, 4);
        /* 右 */
        if (j + 1 < col && (!id || id == 5)) 
            searchStr(i, j + 1, index + 1, 5);
        /* 右下 */
        if (j + 1 < col && i + 1 < row && (!id || id == 6)) 
            searchStr(i + 1, j + 1, index + 1, 6);
        /* 下 */
        if (i + 1 < row && (!id || id == 7)) 
            searchStr(i + 1, j, index + 1, 7);
        /* 左下 */
        if (j - 1 >= 0 && i + 1 < row && (!id || id == 8)) 
            searchStr(i + 1, j - 1, index + 1, 8);
    }
}

上段程式面，str 為找尋字串，W 為字元陣列。

最後，只須在主程式如此呼叫：

gets(str);
len = strlen(str); 
for (j = 0; j < len; j ++)
    str[j] = tolower(str[j]);
isFind = 0;
for (j = 0; j < row && !isFind; j ++)
    for (s = 0; s < col && !isFind; s ++)
    {
        searchStr(j, s, 0, 0);
        if (isFind) printf("%d %d\n", j + 1, s + 1);
    }

By David.K

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

Problem 10004 Bicoloring，著色問題

此題為一老老實實的 m - 著色問題，這用回溯演算法就可以解決了。

首先將節點能連接的通通將值改為 1，因為是雙向的，所以也要將反向連接的也改為 1，C 語言程式碼如下：

int pathNum, f, t;
scanf("%d", &pathNum);
for (i = 0; i < pathNum; i ++)
    scanf("%d %d", &f, &t), W[f + 1][t + 1] = W[t + 1][f + 1] = 1;

利用回溯演算法找出有幾種塗色方式，C 語言程式碼如下：

int promising(int i)
{
    int j;
    for (j = 1; j < i; j ++)
    {
        if (W[i][j] && vcolor[i] == vcolor[j])
            return 0;
    }
    return 1;
}

void m_coloring(int i)
{
    int color, j;
    if (i == n + 1)
        total ++;
    else
    {
        for (color = 1; color <= m; color ++)
        {
            vcolor[i] = color;
            if (promising(i)) m_coloring(i + 1);
        }
    }
}

最後只須在主程式內如此呼叫以及印出：

total = 0;
m_coloring(1);
if (total == 0) printf("NOT BICOLORABLE.\n");
else printf("BICOLORABLE.\n");

By David.K

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

Problem 763 Fibinary Numbers，費氏級數顯示方式

費氏級數進位的有些數值可能會有不只一種情況，例如：10 可表示為 10010 (8 + 2)，但也可表示為 1110 (5 + 3 + 2)，題目會給你兩個費氏級數，請你相加之後，要轉成前者，而不是後者，也就是說，不允許 1 相連。

首先，讀入兩字串，將這兩字串反向擺入一個整數陣列，方便相加：

mIndex = strlen(str);
for (i = mIndex - 1, j = 0; i >= 0 ; i--, j ++)
    m[j] = str[i] - '0';    
memset(str, 0, strlen(str)); 
scanf("%s", str); 
nIndex = strlen(str);
for (i = nIndex - 1, j = 0; i >= 0 ; i--, j ++)
    n[j] = str[i] - '0';

寫一函式，相加兩陣列到 sum 陣列：

void add(int index)
{ 
    int i;
    for (i = 0; i < index; i ++)
        sum[i] = m[i] + n[i];
}

相加之後，就判斷 1 相連的位置，並且使它進位，直到判斷沒有任何數要進位為止。 C 語言程式碼如下：

isChange = 1;
while (isChange)
{
    isChange = 0;
    index = sumLength();  
    for (i = index ; i >= 2; i --)
        if (sum[i] > 1) sum[i]--, sum[i - 1] ++, sum[i - 2] ++, isChange = 1;
    for (i = index; i >= 1; i --)
        if (sum[i] >= 1 && sum[i - 1] >= 1) sum[i]--, sum[i - 1]--, sum[i + 1] ++, isChange = 1;
    if (sum[0] >= 2)
       sum[1] ++, sum[0] -= 2, isChange = 1;
    if (sum[1] >= 2)
       sum[1] -= 2, sum[2] ++, sum[0] ++, isChange = 1;            
}

最後反向印出即可。

By David.K

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

Problem 626 Ecosystem，食物鏈

輸入一 n 值後，讀入 n * n 陣列，例如： n = 3，而陣列內容如下

索引  | 1 | 2 | 3
---------------
1     | 0 | 1 | 0
---------------
2     | 0 | 0 | 1
---------------
3     | 1 | 0 | 0

這例子代表有三種動物，動物 1 吃動物 2，動物 2 吃動物 3，動物 3 吃動物 1。
所以形成一個循環 1 吃 2 吃 3 吃 1，以 1 2 3 表示，但也可以以 2 3 1、 3 1 2 表示，但這種情況只要輸出遞增或遞減的那個。

此題用一巢狀迴圈就可以找出所有食物鏈，假設動物 i 吃動物 j，動物 j 吃動物 k，動物 k 吃動物 i。首先要找尋動物 i 以及動物 j，在嘗試找尋動物 k，最後再判斷是否為遞增或遞減。
尋找動物 k 的方法，我用一函式來找尋， C 語言程式碼如下：

int system[102][102];

int n, count;
void ecosystem(int f, int m)
{
    int i, j, t;
    if (!system[f][m]) return;
    for (t = 0; t < n; t ++)
    {
        if (system[m][t] && system[t][f])
           if (( f > m && m > t ) ||( t > m && m > f ))
           { printf("%d %d %d\n", f + 1, m + 1, t + 1); count ++; }
        
    }
}

最後只須在主程式內呼叫以及輸出：

count = 0;
for (i = 0; i < n; i ++)
    for (j = 0; j < n; j ++)
    {
        ecosystem(i, j);
    }
printf("total:%d\n\n", count); 

By David.K

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

Problem 821 Page Hopping，翻頁

題目輸入整數 i 和整數 j，意思是說第 i 頁翻到第 j 頁需要一次，數量不等，讀到 0 0 結束讀取，若一開始就輸入 0 0 程式就會結束，當我們翻書時，會產生一書的「拍打聲」，所以我們要輸出此書平均會「拍打」幾聲。

此題要先紀錄最大的頁數，並且將所有第 i 頁翻到第 j 頁的資料在索引內的值變為 1，例如：
1 2 2 4 1 3 3 1 4 3 0 0
而陣列內的所有狀態如下：
0 1 1 0
0 0 0 1
1 0 0 0
0 0 1 0
而陣列狀態定義好後，使用「最短路徑演算法」後，再將陣列內的值總合起來除以陣列內有值的個數，答案就會出來了。C 語言程式碼如下：

count = 0, sum = 0; 
for(k = 1; k <= max; k++)
r(i = 1; i <= max; i++)
or(j = 1; j <= max; j++)
        {
            if (i != j && page[i][k] != 0 && page[k][j] != 0)
            {
                int t = page[i][k] + page[k][j];
                if (page[i][j] == 0) page[i][j] = t;
                else if (t < page[i][j]) page[i][j] = t;
            }
        }
or(i = 1; i <= max; i ++)
   for(j = 1; j <= max; j ++)
   {
       int t = page[i][j];
       if (page[i][j] > 0) sum += t, count ++;
   }
printf("Case %d: average length between pages = %.3f clicks\n", caseNum ++,(float)sum / (float)count);

By David.K

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

Problem 808 Bee Breeding，最短移動距離

此題與 Problem 10182 Bee Maja 一樣，要先求出座標以及位置。

而此題座標規則與 10182 有些不同，如下圖：而求出座標以及位置，10182 講得很清楚了，這裡不再多說，只是求出兩座標後要利用以下公式求出距離：
座標 1：(x1, y1)、座標 2：(x2, y2)， dx = x1 - x2, dy = y1 - y2，則距離為： (|dx| + |dy| + |dx + dy|) / 2。
By David.K

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

Problem 10182 Bee Maja，蜜蜂座標的轉換

Maja 是一隻蜜蜂，她和其他數以千計的蜜蜂住在鬧區，這鬧區是一種以六邊形緊鄰的方式排列。
但問題就出在 Willi 告訴 Maja，在哪裡可以與他會面，要知道，Willi 是一個懶惰的蜜蜂，而 Maja 是一個勤勞的蜜蜂，所以他們對於鬧區有不同的座標看待方式。
以下為 Maja 看待鬧區方式：而以下為 Willi 看待鬧區方式：問題就是，我輸入 Willi 座標，請你把它轉換為 Maja 座標。

首先，我們要找出座標規則，如同下圖所示：接著判斷它的移動方向，從 1 開始第一次循環，只跑一次，它是從 0, 0往下，再來往左上、上、右上、右下到 6 為止，接著 7 進入第二循環，跑兩次，往下，左下(注意，右下每次執行階會與循環次數少 1，所以第一次循環沒有執行)、左上、上、右上、右下到 17 為止。如此如此執行到大於等於 100000 為止。
依照以上觀念寫成 C 語言程式碼如下：

#define SIZE 100000

struct point
{
    int x, y;
};
struct point p[SIZE + 1];
int index;
void create()
{
    p[1].x = 0, p[1].y = 0;
    index = 2;
    int nowI = 0, nowJ = 0, count, num;
    for (num = 1; index <= SIZE; num ++)
    {
        for (count = 0; count < num && index <= SIZE; count ++, index ++)
            p[index].x = nowI, p[index].y = ++ nowJ;
        for (count = 0; count < num - 1 && index <= SIZE; count ++, index ++)
            p[index].x = -- nowI, p[index].y = ++ nowJ;
        for (count = 0; count < num && index <= SIZE; count ++, index ++)
            p[index].x = -- nowI, p[index].y = nowJ;
        for (count = 0; count < num && index <= SIZE; count ++, index ++)
            p[index].x = nowI, p[index].y = -- nowJ;
        for (count = 0; count < num && index <= SIZE; count ++, index ++)
            p[index].x = ++ nowI, p[index].y = -- nowJ;
        for (count = 0; count < num && index <= SIZE; count ++, index ++)
            p[index].x = ++ nowI, p[index].y = nowJ;
    }
}

最後在主程式如此呼叫：

create();
int n;
    
while (scanf("%d", &n) == 1)
    printf("%d %d\n", p[n].x, p[n].y);

By David.K

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

Problem 785 Grid Colouring，著色

這題就是 Problem 784 Maze Exploration 的進階版，只比它難一咪咪。

字元 'X' 這次代表框架，此題重點就在於要記錄它著色的字元以及位置，就如同 784 的字元 '*' 一樣，所以宣告陣列有些許的改變。C 語言程式碼如下：

#define ROW 33
#define COL 83
#define SIZE 300
struct point
{    
    char ch;
    int i;
    int j;
};
struct point p[SIZE];
char str[ROW][COL];
int index;

而函式也稍做修改，程式碼如下：

void visit(int i, int j, char ch)
{
    str[i][j] = ch;
    
    if (str[i - 1][j] == ' ') visit(i - 1, j, ch);
    if (str[i + 1][j] == ' ') visit(i + 1, j, ch);
    if (str[i][j - 1] == ' ') visit(i, j - 1, ch);
    if (str[i][j + 1] == ' ') visit(i, j + 1, ch);
}

最後就是要記錄著色的字元以及位置，就請各位參考，在此就不再解說：

int n, len, line = 0, i;
index = 0;
while (gets(str[line]))
{   
    len = strlen(str[line]);
    if (str[line][0] == '_')
    {
        for (i = 0; i < index; i ++)
            visit(p[i].i, p[i].j, p[i].ch);
        for (i = 0; i <= line; i ++)
            puts(str[i]);
        line = 0, index = 0; continue;
    }
    for (i = 0; i < len; i ++)
        if (str[line][i] != ' ' && str[line][i] != 'X') 
        { p[index].ch = str[line][i]; p[index].i = line; p[index].j = i; index ++; }
    line ++;
}

By David.K

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

Problem 784 Maze Exploration，迷宮探索

此題給你一個迷宮，迷宮皆用字元 'X' 圍起，而目前的位置是在字元 '*' (星號)，可以上下左右移動，要找出在這個迷宮所能走到的範圍，並且用字元 '#' 填滿這個範圍。

我們可以先建立一個陣列，題目規定範圍在寬：30、長：80。

#define ROW 33
#define COL 83
char str[ROW][COL];

接著在主程式讀取字串並且記憶字元 '*' 在陣列的位置：

for (line = 0, isStar = 0; ; line ++)
{
    gets(str[line]);
    len = strlen(str[line]);
    if (!isStar)
    {
        for (i = 0; i < len; i ++)
            if (str[line][i] == '*') 
            { startI = line, startJ = i; isStar = 1; break; }
    }
    if (str[line][0] == '_') break;
}

isStar 為判斷字元 '*' 是否出現過，startI、startJ 記錄字元 '*' 在陣列之位置，只要一讀到字元 '_' 便跳出並且計算。
接下來就是將探索地區填滿字元 '#'，其實只要用遞迴就可以解決這個問題，讀入座標，將此位置的字元改為 '#'，並且嘗試上下左右位置是否為 ' '，再將這個位置傳入遞迴。C 語言程式碼如下：

void visit(int i, int j)
{
    str[i][j] = '#';
    
    if (str[i - 1][j] == ' ') visit(i - 1, j);
    if (str[i + 1][j] == ' ') visit(i + 1, j);
    if (str[i][j - 1] == ' ') visit(i, j - 1);
    if (str[i][j + 1] == ' ') visit(i, j + 1);
}

最後只須在主程式內這麼呼叫：

visit(startI, startJ);

By David.K

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

Problem 725 Division

輸入一 n 值，要找出所有 abcde / fghij = n 的數，條件是，abcde 和 fghij 的每個位數不能重複出現，如果不滿五位數，則補 0。此題與 Problem 471 Magic Numbers 相同，如果解了此題，不仿可以解解 471。

找尋此數，因 abcde > fghij，所以 fghij >= 1234，因為如果小於 1234 的數，都會違反條件。

首先，寫一判斷兩數符合條件之函式：

int check(int i, int j)
{
    int tmp, k, repeat[10] = {0};
    for (k = 0 ; k < 5; k ++)
    {
        tmp = i % 10;
        if (repeat[tmp]) return 0;
        repeat[tmp] = 1;
        i /= 10;
        tmp = j % 10;
        if (repeat[tmp]) return 0;
        repeat[tmp] = 1;
        j /= 10;
    }
    return 1;
}

主程式則是要從 fghij = 1234，持續判斷到 abcde >= 100000 為止。 C 語言程式碼如下：

abcde = 1234 * n, fghij = 1234;
count = 0;
if (caseNum ++ != 0) printf("\n");
for (; abcde < 100000; abcde += n, fghij ++)
    if (check(abcde, fghij)) 
        printf("%05d / %05d = %d\n", abcde, fghij, n), count ++;
if (count == 0) printf("There are no solutions for %d.\n", n);

By David.K

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

Problem 466 Mirror, Mirror

此題給你兩種矩形，請你判斷第一種如何旋轉或者水平鏡照，會變成第二種。

例如給你一個 4 * 4 的矩陣，如下：
‧X‧‧
‧X‧X
‧‧‧‧
‧‧X‧
而矩陣的旋轉以及鏡照有以下幾種情況：
(1) 90 Degree Rotation：矩陣向右旋轉 90 度。
‧‧‧‧
‧‧XX
X‧‧‧
‧‧X‧
(2) 180 Degree Rotation：矩陣向右旋轉 180 度。
‧X‧‧
‧‧‧‧
X‧X‧
‧‧X‧
(3) 270 Degree Rotation：矩陣向右旋轉 270 度。
‧X‧‧
‧‧‧X
XX‧‧
‧‧‧‧
(4) Vertical Reflection：水平鏡照，上下如同看鏡子似的，相互鏡照。
‧‧X‧
‧‧‧‧
‧X‧X
‧X‧‧
(5) Combination：水平鏡照加上一個角度的旋轉。(以下是水平鏡照加上右轉 90 度角)
‧‧‧‧
XX‧‧
‧‧‧X
‧X‧‧
(6) Preservation：一開始就和原本的一樣。
(7) Improper：以上狀況都不符合的情況。

其實關鍵就在於你會不會寫轉換函式，寫完幾乎就已經完成了。以下為關鍵函式程式碼：

void rotation90()
{
     int i, j;
     for (i = 0; i < n; i ++)
         strcpy(s[i], replace[i]);
     for (i = 0; i < n; i ++)
         for (j = 0; j < n; j ++)
             replace[i][j] = s[n - j - 1][i];
}

void rotation180()
{
     int i, j;
     for (i = 0; i < n; i ++)
         strcpy(s[i], replace[i]);
     for (i = 0; i < n; i ++)
         for (j = 0; j < n; j ++)
             replace[n - i - 1][j] = s[i][n - j - 1];         
}

void rotation270()
{
     int i, j;
     for (i = 0; i < n; i ++)
         strcpy(s[i], replace[i]);
     for (i = 0; i < n; i ++)
         for (j = 0; j < n; j ++)
             replace[j][i] = s[i][n - j - 1];

}

void reflection()
{
    int i, j;
    for (i = 0; i < n; i ++)
         strcpy(s[i], replace[i]);
    for (i = 0; i < n; i ++)
        for (j = 0; j < n; j ++)
            replace[n - j - 1][i] = s[j][i];
}

By David.K

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

Problem 474 Head / Tails Probability，2 的 -n 次方

要求 2_-n 的指數型態，可以用 double 的 %e 顯示，但格式不太對，而且 2^-1000000 次方的位數太大了，double 接收不了，所以還是乖乖的算出它來。

首先求位數，一般我們用 log₁₀(n) 能求出 n 是幾位數，例如 log₁₀(100) = 2、 log₁₀(1000) = 3、 log₁₀(56565) = 4.7525... 、 ... 等等。
所以可以宣告一整數 power，接收此次 n 值的位數，則位數求法為： (int)ceil(n * log10(2))。

再求 2^-n 的頭幾位數，可以利用公式推導：

          2-n = a
   log10(2-n) = log10(a)
-n * log10(2) = log10(a)
10 -n * log10(2) = a

但如果 n 值越大，a 就越小，所以我們可以加上剛剛求出的位數，將它變成有個位數，則為
10 ^{-n * log₁₀(2) + power}。

最後，不知道是 UVa 答案出了問題，還是題目沒說清楚，在 n = 6時，本來為 1.563e-2，卻為 1.562e-2，所以這要額外判斷。 C 語言程式碼如下：

int power = (int)ceil(n * log10(2));
double d = pow(10, -n * log10(2) + power);
if (n != 6) printf("2^-%d = %.3fe-%d\n", n, d, power);
else printf("2^-6 = 1.562e-2\n");

By David.K

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

Problem 471 Magic Numbers

輸入一個 n 值，請你找出所有 s1 / s2 的數，但有唯一條件，就是以上出現的每個數(n 或 s1 或 s2)，每個位數不會重複出現。例如： 1234567890 就符合條件， 1123 就不符合條件。

首先寫一個檢查位數的函式，符合就回傳 1，反之，回傳 0，C 語言程式碼如下：

int check (long long int n)
{
    int repeat[10] = {0};
    for (; n; n /= 10)
    {
        int tmp = n % 10;
        if (repeat[tmp]) return 0;
        repeat[tmp] = 1;
    }
    return 1;
}

接下來只要用一迴圈，初設 s1 = n, s2 = 1，找尋每個 s1 / s2 = n 的數值，在我實驗看來，s2 不會超過 180000。 C 語言程式碼如下：

long long int s1, s2, limit, n;
scanf("%d", &caseNum);

for (i = 0; i < caseNum; i ++)
{
    scanf("%lld", &n);
    limit = 180000;
    if (i != 0) printf("\n");
    for (s2 = 1, s1 = n; s2 < limit; s1 += n, s2 ++)
    {
        if (check(s1) && check(s2))
            printf("%lld / %lld = %lld\n", s1, s2, n);
    }
}

By David.K

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

Problem 459 Graph Connectivity，畫連接線

此題要用到回溯演算法，讀入第一個英文字母後，決定陣列的範圍，我們可以宣告整數陣列為 W[27][27]，因為大寫字母最大到 Z(26)，再接下來有 0 到多行，每行都有兩個大寫英文 ch1 和 ch2，代表連接線，此時我們可以改變 W 陣列內的值，將 W[ch1 - 'A'][ch2 - 'A'] = W[ch2 - 'A'][ch1 - 'A'] = 1，因為連接線是無向的，也藉此表示這兩點有連接。

再來宣告一整數陣列 v[27]，紀錄每個連結點是否有拜訪過，一旦拜訪，就不再拜訪，當拜訪每一個節點，改變它在 v 陣列位置的值為 1。接著再找尋它每一個能連結的點，就再將它每個能連結點 v 陣列位置的值改為 1，再繼續找尋這些連結點能連結的點。如此如此做下去，結果就會出來了。

以下為拜訪函式：

int m;
int W[27][27];
int v[27];
void visit(int n)
{
     v[n] = 1;
     int i, j;
     for (i = 0; i <= m; i ++)
         if (v[i] == 0 && W[n][i] == 1)
             visit(i);
}

在主程式如此呼叫此函式：

int n, i, j;
char ch[3];
scanf("%d", &n);
for (j = 0; j < n; j ++)
{
    int count = 0, isCase = 0;  
    memset(v, 0, sizeof(v));
    memset(W, 0, sizeof(W));
    while (gets(ch))
    {
        int len = strlen(ch);
        if (len == 0) 
        { 
           if (isCase)
           {
               for (i = 0; i <= m; i ++)
               {
                   if (v[i] == 0)
                       visit(i), count ++;
               }
               if (j != 0) printf("\n");
               printf("%d\n", count);
               isCase = 0;
               break;
           } 
        }
        if (len == 1) isCase = 1, m = ch[0] - 'A';
        if (len > 1)
        {
            int node1 = ch[0] - 'A';
            int node2 = ch[1] - 'A';
            W[node1][node2] = W[node2][node1] = 1;
        }
    }
    if (isCase)
    {
        for (i = 0; i <= m; i ++)
        {
            if (v[i] == 0)
                visit(i), count ++;
        }
        if (j != 0) printf("\n");
        printf("%d\n", count);
        isCase = 0;
    }
}

By David.K

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

Problem 465 Overflow，溢出

此題就是給你兩個數，可能相乘也可能相加，請你判斷它第一個數或第二個數會不會超出 2³¹，或者計算結果會超出 2³¹。
若第一個數超出 2³¹，輸出 first number too big。
若第二個數超出 2³¹，輸出 second number too big。
若第二個數超出 2³¹，輸出 result too big。

其實這題我本來想用大數來算，但發現用 double 運算也可以，所以就用 double， C 語言程式碼如下：

while (gets(str))
{
    double inf = (double)INT_MAX, n1, n2;
    printf("%s\n", str);
    sscanf(str, "%lf %c %lf", &n1, &ch, &n2);
    if (n1 > inf) printf("first number too big\n");
    if (n2 > inf) printf("second number too big\n");
    
    if (ch == '+')
    {
        if (n1 + n2 > inf) printf("result too big\n");
    }
    if (ch == '*')
    {
        if (n1 * n2 > inf) printf("result too big\n");
    }
}

By David.K

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

Problem 445 Marvelous Mazes，畫迷宮

題目有幾項規則，出現一連串的數字的總和，決定一連串數字後出現的字元要印出幾次。
如果字元為 A-Z，則直接印出。
如果字元為 b，則印出空白。
但如果遇到 '!' 或 '\n' ( 換行字元 )，都要換行。

最後， C語言程式碼如下：

while (gets(str))
{
    for (i = 0, count = 0; (ch = str[i]); i ++)
    {
        if (isdigit(ch))
            count += ch - '0';
        if (isupper(ch) || ch == '*' | ch == 'b')
        {
            if (ch != 'b')
            {
                while(count)
                    printf("%c", ch), count --;
            }
            else
            {
                while(count)
                    printf(" "), count --;
            }
        }
        if (ch == '!') printf("\n");
    }
    printf("\n");
}

By David.K

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

Problem 443 Humble Numbers，爛數字

此題跟 Problem 136 Ugly Numbers，簡直一模一樣，只是這一次要求出前 5842 個只有 2 或 3 或 5 或 7 的質因數的數字。這裡不多說，程式碼如下：

int humble[5843];

int min(int a, int b)
{
    return a > b ? b : a;
}

void create()
{
    int num = 0, p2, p3, p5, p7, n;
    humble[1] = p2 = p3 = p5 = p7 = n = 1;
    while (1)
    {
        humble[++ n] = min(2 * humble[p2], 
                       min(3 * humble[p3], 
                       min(5 * humble[p5], 7 * humble[p7]) ));
        if (humble[n] == 2 * humble[p2]) p2 ++;
        if (humble[n] == 3 * humble[p3]) p3 ++;
        if (humble[n] == 5 * humble[p5]) p5 ++;
        if (humble[n] == 7 * humble[p7]) p7 ++;
        if (n == 5842) break;
    }
}

void printNumber(int n)
{
    int s = n % 10;
    int h = n % 100;
    printf("The %d", n);
    if (h == 11) printf("th");
    else if (h == 12) printf("th"); 
    else if (h == 13) printf("th"); 
    else if (s == 1) printf("st");
    else if (s == 2) printf("nd");
    else if (s == 3) printf("rd");
    else printf("th"); 
    printf(" humble number is %d.\n", humble[n]);
}

int main()
{
    create();
    int n;
    while (scanf("%d", &n) == 1 && n)
    {
        printNumber(n);
    }
    return 0;
}

By David.K

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

Problem 442 Matrix Chain Multiplication，矩陣相乘

此題用字串做四則運算，所以要一步一步的讀取字串內容，再算出矩陣相乘的總次數。
矩陣 A 為 m1 * n1，矩陣 B 為 m2 * n2，假設 n1 = m2，則 A * B 的相乘次數為 m1 * n1 * m2 或 m1 * n2 * m2。

一開始先建構一個結構，裡面記錄矩陣字元、矩陣寬、矩陣長、相乘次數，C 語言程式碼如下：

struct matrix
{
    char ch;
    int row;
    int col;
    int count;
};
struct matrix m[26], stack[200];

接著在主程式讀入所有矩陣的資料：

scanf("%d", &n);
getchar();
for (i = 0; i < n; i ++)
{
    scanf("%c %d %d", &ch, &row, &col);
    getchar();
    int index = ch - 'A'; 
    m[index].ch = ch, m[index].row = row, m[index].col = col; 
}

再來，就是開始計算的時候了，剛剛建構結構時，多見了一個 stack 陣列，那是要將一步一步讀取的資料堆在這個陣列。

一開始將 index 定義為 0，index 為 stack 陣列索引。
●如果遇到字元 '('，將 '(' 加入 stack， index 加 1。
●如果遇到字元為 A-Z，判斷 stack 的最上面索引的字元也為 A-Z，就將兩個矩陣相乘，並且判斷兩矩陣相乘會不會違反規則，若不會，則將相乘次數累計在最上面索引的相乘次數；若最上面索引的字元不為 A-Z，則將此次的矩陣資料加入 stack， index 加 1。
●如果遇到字元 ')'，先判斷 stack 是否為空，為空則錯誤；再判斷最上面索引的字元若為 ')'，則 index 減 1。最後判斷最上面索引的字元為 A-Z 和次上面索引的字元為 '('，就將最上面索引的資料下推，index 減 1，接著判斷次上面索引的字元為 A-Z，再將最上面和次上面的矩陣相乘，相乘次數累計在次上面索引，再將 index 減 1。

以上看不懂沒關係，提供程式碼最實在，由以上觀念寫成 C 語言程式碼如下：

while (gets(str))
{
    int count = 0, error = 0, index = 0;
    int row = 0, col = 0;
    for (i = 0; (ch = str[i]); i ++)
    {
        if (ch == '(') stack[index ++].ch = ch;
        if (isupper(ch))
        {
            int s = ch - 'A';
            row = m[s].row, col = m[s].col;
            if (isupper(stack[index - 1].ch))
            {
                if (stack[index - 1].col != row)
                { error = 1; break; }
                stack[index - 1].count += stack[index - 1].row * row * col;
                stack[index - 1].col = col; 
            }
            else
            {
                stack[index].ch = ch;
                stack[index].row = row;
                stack[index].col = col;
                stack[index].count = 0;
                index ++;  
            }
        }
        if (ch == ')') 
        {
            if (index - 1 < 0) { error = 1; break; }
            if (stack[index - 1].ch == '(') index --;
            if (index - 2 >= 0 && 
                isupper(stack[index - 1].ch) && stack[index - 2].ch == '(')
            {
                stack[index - 2].ch = stack[index - 1].ch;
                stack[index - 2].row = stack[index - 1].row;
                stack[index - 2].col = stack[index - 1].col;
                stack[index - 2].count = stack[index - 1].count;
                index --;
                if (isupper(stack[index - 2].ch))
                {
                    row = stack[index - 1].row;
                    col = stack[index - 1].col;
                    count = stack[index - 1].count;
                    
                    if (stack[index - 2].col != row)
                    { error = 1; break; }
                    stack[index - 2].count += (count + stack[index - 2].row * row * col);
                    stack[index - 2].col = col;
                    index --;
                }
            }
        }
    }
    if (error == 0) printf("%d\n", stack[0].count);
    else if (error) printf("error\n");
}

By David.K

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

Problem 406 Prime Cuts，中間的質數

建立質數表後，再找尋左右兩側印出的點，然後印出就好了。

首先建立質數表，要注意要將 1 也加入，在此題 1 也為質數， C 語言程式碼如下：

#define MAXSIZE  1010

int prime[MAXSIZE + 1];
int prime_table[MAXSIZE], prime_table_len = 0;

int makeprime(){
    int i, j;
    prime_table[prime_table_len ++] = 1;
    prime_table[prime_table_len ++] = 2;
    for(i = 3; i <= MAXSIZE; i += 2)
        if(!prime[i]){
            for(j = i + i; j <= MAXSIZE; j += i)
                prime[j] = 1;
            prime_table[prime_table_len ++] = i;
        }
}

輸入 n 值後，先找出小於等於 n 值得質數，再找出左右兩側印出的索引，最後利用這兩索引，印出在這兩索引之間的質數，C 語言程式碼如下：

while (scanf("%d %d", &n, &c) == 2)
{
    for (len = 0; n >= prime_table[len]; len ++)
        ;
    if (len % 2) 
    {
        if ( (c * 2 - 1) >= len) left = 0, right = len - 1;
        else left = len / 2 - (c - 1), right = len / 2 + (c - 1);
    }
    else
    {
        if ( c * 2 >= len) left = 0, right = len - 1;
        else right = len / 2 + (c - 1), left = right - 2 * c + 1;
    }
    printf("%d %d:", n, c);
    for (i = left; i <= right; i ++)
        printf(" %d", prime_table[i]);
    printf("\n\n");
}

By David.K

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

Problem 401 Palindromes，判斷字的類型

Character	Reverse	Character	Reverse	Character	Reverse
A	A	M	M	Y	Y
B		N		Z	5
C		O	O	1	1
D		P		2	S
E	3	Q		3	E
F		R		4
G		S	2	5	Z
H	H	T	T	6
I	I	U	U	7
J	L	V	V	8	8
K		W	W	9
L	J	X	X

(表一)

STRING	CRITERIA
" -- is not a palindrome."	if the string is not a palindrome and is not a mirrored string
" -- is a regular palindrome."	if the string is a palindrome and is not a mirrored string
" -- is a mirrored string."	if the string is not a palindrome and is a mirrored string
" -- is a mirrored palindrome."	if the string is a palindrome and is a mirrored string

(表二)

此題輸入一字串，要判斷它是如表二所說的哪一種字串。
第一種：不是回文字串，意思就是說它是下述三種都不符合的情況下，
        才為這種字串。
第二種：為一正規回文字串，回文字就是對稱的字串，也就是不管你從
        左邊或右邊讀，都是一樣的，例如字串 ABCBA 、 ABCCBA，皆
        是回文字。
第三種：為一鏡照字，依照表一鏡照對照表可以觀察鏡照字，而鏡照字
        串就是從左邊讀會與鏡照後從右邊讀的字串一樣。
第四種：為一鏡照回文字，綜合第二、第三種條件的字串。

一開始可以寫一鏡照轉換函式，傳入字元即可傳出鏡照字元，如果找不到，回傳空白字串，C 語言程式碼如下：

char mirroredChar(char ch)
{
    if (ch == 'A') return 'A';
    if (ch == 'E') return '3';
    if (ch == '3') return 'E';
    if (ch == 'H') return 'H';
    if (ch == 'I') return 'I';
    if (ch == 'J') return 'L';
    if (ch == 'L') return 'J';
    if (ch == 'M') return 'M';
    if (ch == 'O') return 'O';
    if (ch == 'S') return '2';
    if (ch == '2') return 'S';
    if (ch == 'T') return 'T';
    if (ch == 'U') return 'U';
    if (ch == 'V') return 'V';
    if (ch == 'W') return 'W';
    if (ch == 'X') return 'X';
    if (ch == 'Y') return 'Y';
    if (ch == 'Z') return '5';
    if (ch == '5') return 'Z';
    if (ch == '1') return '1';
    if (ch == '8') return '8';
    if (ch == '0') return '0';
    return ' ';
}

接著，定義兩整數，用來判斷是否為違規鏡照字或回文字的規定，int isPalindrome = 1, isMirrored = 1;，讀入字串後，判斷字串中間點( 如果從字串兩側進行也可以 )，定義左側字串索引 left，右側字串索引 right，依序往左右進行判斷。如果此次 left 索引字元鏡照後不等於 right 索引字元，則違規鏡照字的規定，定義 isMirrored = 0;；若此次的 left 索引字元不等於 right 索引字元，則違規回文字的規定，定義 isPalindrome = 0;。如此判斷下去，直到超出索引位置之前。以上觀念寫成 C 語言程式碼如下：

int left, right;  
len = strlen(str);

/* 判斷中間點 */
if (len % 2) left = len / 2, right = left;
else left = len / 2 - 1, right = left + 1;

char leftCh, rightCh;
for ( ;left >= 0 && right < len; left --, right ++)
{
    leftCh = str[left];
    rightCh = str[right];
    if ( mirroredChar(leftCh) != rightCh ) isMirrored = 0;
    if ( leftCh != rightCh ) isPalindrome = 0;
}
printf("%s -- ", str);
if (isMirrored && isPalindrome) printf("is a mirrored palindrome.");
else if (isMirrored) printf("is a mirrored string.");
else if (isPalindrome) printf("is a regular palindrome.");
else printf("is not a palindrome.");
printf("\n\n");

By David.K

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

Problem 572 Oil Deposits，石油區塊

此題我利用遞迴解決問題，似乎還有很多種方法，不過我都不太了解就是了，因為我還太嫩 '^^a。

讀入一地區的狀態，字元 '*' 代表沒油，字元 '@' 代表有油。只要是 @ 兩兩相鄰的區域就代表同一區塊，題目就是問你說在這一地區之中，有幾個石油區塊。

寫一可以找出同一石油區塊的函式，找到之後將所有字元便成 '*'：

#define SIZE 102

int m, n;
char Oil[SIZE][SIZE];
void visit(char Oil[][SIZE], int i, int j)
{
    Oil[i][j] = '*';
    int left = (j - 1 >= 0), right = (j + 1 < n), 
        up = (i - 1 >= 0), down = (i + 1 < m); 
        
    if (left && Oil[i][j - 1] == '@')  /* 左 */
        Oil[i][j - 1] = '*', visit(Oil, i, j - 1);
    if (left && down && Oil[i + 1][j - 1] == '@') /* 左下 */
        Oil[i + 1][j - 1] = '*', visit(Oil, i + 1, j - 1);
    if (down && Oil[i + 1][j] == '@') /* 下 */  
        Oil[i + 1][j] = '*', visit(Oil, i + 1, j);
    if (right && down && Oil[i + 1][j + 1] == '@') /* 右下 */ 
        Oil[i + 1][j + 1] = '*', visit(Oil, i + 1, j + 1);
    if (right && Oil[i][j + 1] == '@') /* 右 */ 
        Oil[i][j + 1] = '*', visit(Oil, i, j + 1);
    if (right && up && Oil[i - 1][j + 1] == '@') /* 右上 */ 
        Oil[i - 1][j + 1] = '*', visit(Oil, i - 1, j + 1);
    if (up && Oil[i - 1][j] == '@') /* 上 */ 
        Oil[i - 1][j] = '*', visit(Oil, i - 1, j);
    if (left && up && Oil[i - 1][j - 1] == '@') /* 左上 */ 
        Oil[i - 1][j - 1] = '*', visit(Oil, i - 1, j - 1);
}

最後，主程式只需要如此呼叫即可：

int pocketNum = 0;  
for (i = 0; i < m; i ++)
    scanf("%s", Oil[i]);
for (i = 0; i < m; i ++)
    for (j = 0; j < n; j ++)
        if (Oil[i][j] == '@')
            pocketNum ++, visit(Oil, i, j);
printf("%d\n", pocketNum);

By David.K

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

Problem 573 The Snail，井底的蝸牛

給你井的高度 H、蝸牛白天上升高度 U、蝸牛晚上下降高度 D、蝸牛疲勞因子 F。
例如給你一隻蝸牛的數據 H = 6, U = 3, D = 1, F = 10。而這隻蝸牛會如以下表顯示，在第 3 天爬出井。

Day	Initial Height	Distance Climbed	Height After Climbing	Height After Sliding
1	0'	3'	3'	2'
2	2'	2.7'	4.7'	3.7'
3	3.7'	2.4'	6.1'	-

其中要注意的就是疲勞因子是以百分比去計算，還有如果因為疲勞而使得白天上升高度變成負值，就使白天上升高度為 0。

程式碼如下：

while (scanf("%f %f %f %f", &H, &U, &D, &F) == 4 && H != 0)
{
    int days = 1;
    float nowHigh = 0.0, sub = U * F / 100;
    while (1)
    {
        nowHigh += U;
        if (nowHigh > H) { printf("success on day %d\n", days); break;}
        nowHigh -= D;
        if (nowHigh < 0) { printf("failure on day %d\n", days); break;}
        U -= sub;
        if (U < 0) U = 0;
        days ++;
    }
}

By David.K

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

Problem 534 Frogger，蛙跳的最小距離

此題給你一些石頭的座標，而要從第一顆石頭跳到第二顆石頭所用最小距離是多少 ( 注意：是最小，不是最短 )。舉個例子，就拿第二個輸入範例來說，
3
17 4 <- 第一顆石頭 ( Freddy所在之石 )
19 4 <- 第二顆石頭 ( Fiona所在之石 )
18 5 <- 第三顆石頭

我們可以簡略算出 1 <--> 2 距離為 2，2 <--> 3 距離為 1.41421，3 <--> 1 距離為 1.41421。如果以最短路徑來說，從 1 直接跳到 2 最快。但以最小距離來說，從 1 跳到 3 再跳到 2，所用只要用 1.41421 的距離便可跳到 2，若直接從 1 跳到 2，便會花上 2.0 距離之長。這就不符合我們所說的最小距離。

一開始我們先將所有石頭之間的距離放入陣列，再用「最小路徑演算法」便可求出最小距離，C 語言程式碼如下：

for (i = 0; i < n; i ++)
    scanf("%f %f", &pt[i][0], &pt[i][1]);
for (i = 0; i < n; i ++)
{
    W[i][i] = 0;
    for (j = i + 1; j < n; j ++)
    {
        W[i][j] = sqrt( (pt[i][0] - pt[j][0]) * (pt[i][0] - pt[j][0]) + 
                        (pt[i][1] - pt[j][1]) * (pt[i][1] - pt[j][1]) );
        W[j][i] = W[i][j];               
    }
}
for (k = 0; k < n; k ++)
    for (i = 0; i < n; i ++)
        for (j = 0; j < n; j ++)
        {
            W[i][j] = min(W[i][j], max(W[i][k] , W[k][j]));
        }
printf("Scenario #%d\n", caseNum ++);        
printf("Frog Distance = %.3f\n\n", W[0][1]);

By David.K

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

Problem 729 The Hamming Distance Problem

此題題目我看的沒有很清楚，但是一看它的輸出入就知道它輸入兩個整數 N 和 H 後，N 為字串長度，H 為 1 的數量，例如：N = 3, H = 2，所以一開始就是 011 為初始字串。要請你求出這字串的所有不重複的排列組合。

一開始要先將初始字串設定好：

scanf("%d %d", &m, &h);
for (j = 0; j < m; j ++)
{
    if (j < m - h) str[j] = '0';
    else str[j] = '1';
}
str[m] = '\0';

再用與 Problem 146 的 next_permutation 函式或 C ++ 中的 next_permutation 的方法，持續找尋下一組的排列組合並且印出，直到找不到為止。C 語言程式碼如下：

void swap(int i, int j)
{
     char tmp;
     tmp = str[i];
     str[i] = str[j];
     str[j] = tmp;
} 

int next_permutation()
{
     int i, j, k;
     int length;
     length = strlen(str);
     for(i = length - 1;i > 0 ; --i)
      if(str[i - 1] < str[i]) break;
     j = i;
     if(j == 0) return 0;
     for(i = length - 1;i > 0; --i)
      if(str[j - 1] < str[i]) break;
     k = i;
     swap(j - 1, k);
     for(i = j, j = length - 1;i < j; ++ i, -- j)
      swap(i, j);
   return 1;
}

最後只需要在主程是內如此呼叫：

printf("%s\n", str);
while (next_permutation())
{
    printf("%s\n", str);
}

By David.K

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

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