Test Message

d250: 94北縣賽-2-數獨問題 (Sudoku)

內容

數獨 ”sudoku”來自日文，其概念源自「拉丁方塊」，是十八世紀瑞士數學家

歐拉發明的。遊戲規則很簡單：在九個九宮格里， 分別填入 1 到 9 的數字，讓每個
數字在每個行、列及九宮格里都只出現一次。謎題中會預先填入若干數字，但有部
分數字尚未填入，玩家得依謎題中數字分佈的狀況，推敲出尚未出現的數字。現在
我們簡化數獨的問題，假設九宮格中每一行及每一列尚未出現的數字都只有一個。
請你寫一個程式，從檔案讀入一個數獨題目，找出每一行尚未出現的數值。
如以下之數獨題目範例：

2 8 1 6 7 3 9 4
6 4 3 2 8 7 1 5
1 7 3 4 9 2 6 8
3 4 5 6 8 1 7 2
8 1 7 3 4 9 5 6
2 5 6 7 1 9 4 3
4 3 5 8 1 6 2 9
7 6 2 9 5 3 4 1
9 8 1 6 4 2 5 3

則第一列之空格應填入 5，第二列之空格應填入 9，第三列之空格應填入 5，第四列
之空格應填入 9，第五列之空格應填入 2，第六列之空格應填入 8，第七列之空格應
填入 7，第八列之空格應填入 8，第九列之空格應填入 7。

填滿結果如以下所示

5 2 8 1 6 7 3 9 4
6 4 9 3 2 8 7 1 5
1 7 3 4 9 5 2 6 8
3 9 4 5 6 8 1 7 2
8 1 7 2 3 4 9 5 6
2 5 6 7 1 9 4 8 3
4 3 5 8 7 1 6 2 9
7 6 2 9 5 3 8 4 1
9 8 1 6 4 2 5 3 7

輸入

每個測試檔案中共有九行，每一行中有 9 個連續且不重複的個位數，對應到九宮格
中的每一列。其中 8 個數字為 1 到 9 之間的數字，另外有一個數字為 0，表示空白
的位置。

028167394
640328715
173490268
304586172
817034956
256719403
435801629
762953041
981642530

輸出

依序輸出各列空白的空位應該填入的個位數。

5
9
5
9
2
8
7
8
7

解題思路

數獨每行元素必為 1~9 各一個，所以每行的總和為 45。

因此將 45 減去所有元素，剩下的值即是沒有填入的數，輸出該值即可。

完整程式碼

AC (2ms, 84KB)
#include <stdio.h>

int main()
{
    int ans;
    char input[10], output[2] = { 0 };
    while (gets(input))
    {
        ans = 45;
        for (int i = 0; i < 9; i++)
            ans -= input[i] ^ '0';
        output[0] = ans | '0';
        puts(output);
    }
    return 0;
}
閱讀更多

c780: 106北二5.炮打眾卒遊戲

內容

img1
img2

輸入

測試資料只有一行,有兩個數字 n 及 m,
表示棋盤大小為 n × m,
其中 1 ≤ n ≤ 8,1 ≤ m ≤ 8 且 n × m ≤ 42。
這兩個數字之間用空格(white space)隔開。

範例輸入一：
3 5

範例輸入二：
4 3

輸出

輸出資料為一個正整數,表示一開始在左上角的炮能吃到最多顆卒的數目。

範例輸出一：
7

範例輸出二：
5

解題思路

依照題意使用 DFS 列舉所有可能性後輸出最大值即可。

完整程式碼

AC (0.1s, 104KB)
#include <stdio.h>
#include <memory.h>

int n, m, best;
char table[10][10];

void serch(int x, int y, int cont)
{
    if (cont > best)
        best = cont;
    int i;
    table[x][y] = 0;
    for (i = x + 1; i < n && !table[i][y]; ++i)
        ;
    while (++i < n)
    {
        if (table[i][y])
        {
            serch(i, y, cont + 1); break;
        }
    }
    for (i = x - 1; ~i && !table[i][y]; --i)
        ;
    while (--i >= 0)
    {
        if (table[i][y])
        {
            serch(i, y, cont + 1); break;
        }
    }
    for (i = y + 1; i < m && !table[x][i]; ++i)
        ;
    while (++i < m)
    {
        if (table[x][i])
        {
            serch(x, i, cont + 1); break;
        }
    }
    for (i = y - 1; ~i && !table[x][i]; --i)
        ;
    while (--i >= 0)
    {
        if (table[x][i])
        {
            serch(x, i, cont + 1); break;
        }
    }
    table[x][y] = 1;
}

int main()
{
    scanf(" %d %d", &n, &m);
    for (int i = 0; i < n; ++i)
        memset(table[i], 1, m);
    serch(0, 0, 0);
    printf("%d\n", best);
    return 0;
}
閱讀更多

b689: 2. 棕櫚迷宮

內容

img1

輸入

7 9
#########
##.....##
##.###.##
##.#...##
##.#.##..
#..#....#
#########

7 9
######.##
##.....##
##.####.#
##.#....#
##.#.##.#
#..#....#
#########

10 10
##########
#....#####
#.##.....#
#...####.#
#######..#
##....#.##
##.##.#..#
##.##.##.#
##..#....#
###.######

輸出

6 2
6 2
4 4

解題思路

題目保證單向、無叉路且僅有一個入口，所以用 dfs 遍歷到最深處後輸出該點即可。

完整程式碼

AC (2ms, 108KB)
#include <stdio.h>

int x, y;
char map[25][25];

void dfs()
{
    map[x][y] = '#';
    if (map[x + 1][y] == '.')
        ++x, dfs();
    else if (map[x - 1][y] == '.')
        --x, dfs();
    else if (map[x][y + 1] == '.')
        ++y, dfs();
    else if (map[x][y - 1] == '.')
        --y, dfs();
}

void getStart(int n, int m)
{
    for (int i = 0; i <= n; i++)
    {
        if (map[i][0] == '.')
        {
            x = i, y = 0; return;
        }
        else if (map[i][m] == '.')
        {
            x = i, y = m; return;
        }
    }
    for (int i = 1; i < m; i++)
    {
        if (map[0][i] == '.')
        {
            x = 0, y = i; return;
        }
        else if (map[n][i] == '.')
        {
            x = n, y = i; return;
        }
    }
}

int main()
{
    int n, m;
    while (scanf(" %d %d", &n, &m) == 2)
    {
        getchar();
        for (int i = 0; i < n; i++)
            gets(map[i]);
        getStart(n - 1, m - 1);
        dfs();
        printf("%d %d\n", x + 1, y + 1);
    }
    return 0;
}
閱讀更多

b520: 樂透-商競103

內容

最近在練「高職的商業技藝競賽」題目,較「高中資訊學科競賽」簡單，適合初學者練習

今彩 539 是一種樂透投注遊戲，投注者必須從 01~39 的號碼中任選 5 個不同的號碼進行投注。為了方便投注者對獎，所以計算開獎號碼和投注者任選的 5 個不同號碼，用程式計算開獎號碼和投注者 5 個號碼，對中幾個號碼。

輸入

第一列的數字 n 代表有幾組資料要測試，1<=n<=5 。第二列起為測試資料。
每組測試資料中有二列，第一列 5 的數字，代表開獎號碼，第二列 5 的數字，投注者任選的 5 個不同號碼，各個號碼間以“, ”隔開。

3
01, 07, 28, 29, 30
01,07 , 29, 30, 36
22, 23,24,39 , 07
01,22 , 23, 24, 25
21 ,22, 23,24,32
01,02,03 , 04,05

輸出

計算每組測試資料中，開獎號碼和投注者的 5 個號碼，用程式計算投注者 5 個號碼中，有幾個號碼有開出。
例如在這組資料中：
01, 07, 28, 29, 30
01, 07, 29, 30, 36
輸出 4

例如在這組資料中：
21, 27, 29, 30, 35
01, 07, 29, 31, 37
輸出 1

例如在這組資料中：
21, 22, 23, 24, 32
01, 02, 03, 04, 05
輸出 0

4
3
0

解題思路

用 scanf() 自帶的格式化工具處理輸入，之後用迴圈判斷即可。

完整程式碼

AC (2ms, 112KB)
#include <stdio.h>

int main()
{
    int n, lhs[5], rhs[5], count;
    scanf(" %d", &n);
    while (n--)
    {
        scanf(" %d , %d , %d , %d , %d", &lhs[0], &lhs[1], &lhs[2], &lhs[3], &lhs[4]);
        scanf(" %d , %d , %d , %d , %d", &rhs[0], &rhs[1], &rhs[2], &rhs[3], &rhs[4]);
        count = 0;
        for (int i = 0; i < 5; i++)
        {
            for (int j = 0; j < 5; j++)
            {
                if (lhs[i] == rhs[j])
                {
                    count++;
                    break;
                }
            }
        }
        printf("%d\n", count);
    }
    return 0;
}
閱讀更多

e024: 少年πの超大數運算(1)

內容

大家對大數運算肯定不陌生

我就不解釋了

大家請看題目

輸入

給你兩個數 n,m (0<n,m<=100000),求 n^m

一行兩個以空白隔開的正整數,以 0 0 結尾

1 1
1 2
1 10000
0 0

輸出

輸出 n^m

1
1
1

解題思路

先建好一個有乘法的大數結構，再用大數乘法配合快速冪算出答案後輸出即可。

以下是優化部分

  1. 大數用千萬進制做完乘法後再進位速度遠高於十億進制一邊乘一邊進位。

  2. 除法和取餘運算很久，改成用除法得到商後再將原數減去除法得到的商乘上一千萬，也就是將

    a = n / 10;
    b = n % 10;

    改成

    a = n / 10;
    b = n - (a * 10);

    不過 10 要改成 1000 萬

  3. 乘法用左移運算加速

  4. 用指標減少記憶體操作量

  5. 輸入輸出優化

第一項特別重要，它讓我從 TLE(10s) 變成 AC(2.3s)，其餘的不做應該也能過但時間就不會太好看。

完整程式碼

AC (1.9s, 2.2MB)
#pragma GCC optimize(3)
#include <stdio.h>
#include <memory.h>
#define BUFSIZ 1048576
#define MOD 10000000
#define MUTMOD(x) ((x<<24)-(x<<22)-(x<<21)-(x<<19)+(x<<16)-(x<<14)-(x<<13)-(x<<11)-(x<<8)-(x<<7))

typedef struct BigNum
{
    unsigned long long Num[72000];
    int Last;
}BigNum;

BigNum list[3], * n = &list[0], * ans = &list[1], * tmp = &list[2];
char output[500050];

inline char readChar()
{
    static char buffer[BUFSIZ], * now = buffer + BUFSIZ, * end = buffer + BUFSIZ;
    if (now == end)
    {
        if (end < buffer + BUFSIZ)
            return EOF;
        end = (buffer + fread(buffer, 1, BUFSIZ, stdin));
        now = buffer;
    }
    return *now++;
}

inline char readUInt(unsigned int* dst)
{
    register char ch;
    while ((ch = readChar()) < '0')
        if (ch == EOF) return 0;
    *dst = ch ^ '0';
    while ((ch = readChar()) >= '0')
        * dst = (*dst << 3) + (*dst << 1) + (ch ^ '0');
    return 1;
}

inline BigNum* BigMult(BigNum* dst, BigNum* times)
{
    memset(tmp, 0, sizeof(BigNum));
    tmp->Last = dst->Last + times->Last;
    register unsigned long long div;
    for (int i = 0; i <= dst->Last; i++)
    {
        if (dst->Num[i])
        {
            for (int j = 0; j <= times->Last; j++)
            {
                if (times->Num[j])
                    tmp->Num[i + j] += dst->Num[i] * times->Num[j];
            }
        }
    }
    for (int i = 0; i <= tmp->Last; i++)
    {
        if (tmp->Num[i] >= MOD)
        {
            div = tmp->Num[i] / MOD;
            tmp->Num[i] = tmp->Num[i] - MUTMOD(div);
            tmp->Num[i + 1] += div;
            if (tmp->Last < i + 1)
                tmp->Last = i + 1;
        }
    }
    BigNum* res = tmp;
    tmp = dst;
    return res;
}

void pow(BigNum* dst, BigNum* src, int m)
{
    dst->Num[0] = 1, dst->Last = 0;
    for (;; m >>= 1)
    {
        if (m & 1)
        {
            dst = BigMult(dst, src);
            if (m == 1)
                break;
        }
        src = BigMult(src, src);
    }
    ans = dst;
    n = src;
}

void putUBigNum(char buffer[], BigNum* src)
{
    register char* st = buffer;
    register unsigned long long div1, div2;
    for (int i = src->Last; ~i; i--, st += 7)
    {
        st[6] = (src->Num[i] - ((div1 = src->Num[i] / 10) << 3) - (div1 << 1)) | '0';
        st[5] = (div1 - ((div2 = div1 / 10) << 3) - (div2 << 1)) | '0';
        st[4] = (div2 - ((div1 = div2 / 10) << 3) - (div1 << 1)) | '0';
        st[3] = (div1 - ((div2 = div1 / 10) << 3) - (div2 << 1)) | '0';
        st[2] = (div2 - ((div1 = div2 / 10) << 3) - (div1 << 1)) | '0';
        st[1] = (div1 - ((div2 = div1 / 10) << 3) - (div2 << 1)) | '0';
        st[0] = (div2 - ((div1 = div2 / 10) << 3) - (div1 << 1)) | '0';
    }
    *st = '\0', st = buffer;
    while (*st == '0')
        st++;
    puts(st);
}

int main()
{
    int m;
    while ((readUInt(&n->Num[0]), readUInt(&m)) && n->Num[0] + m)
    {
        n->Last = 0;
        pow(ans, n, m);
        putUBigNum(output, ans);
    }
    return 0;
}
閱讀更多

d734: 另類Hanoi

內容

設有 n 個大小不同的中空圓盤，按從小到大的順序從 1 到 n 編號。將這 n 個圓盤任意的迭套在三根立柱上，立柱的編號依次為 a、b、c ，這個狀態稱為初始狀態。

現在要求找到一種步數最少的移動方案，使得從初始狀態轉變為目標狀態。

移動時有如下要求：

  • 一次只能移動一個盤。

  • 不允許把大盤移到小盤上面。

輸入

第一行數字 n(1<=n<=20)，表示狀態中圓盤總數。

第二行表示初始狀態，有 n 個數字，第 i 個數字 a[i]表示第 i 個圓盤放在第 a[i]個立柱上。

第三行表示目標狀態，有 n 個數字，第 i 個數字 b[i]表示第 i 個圓盤放在第 b[i]個立柱上。

不必 EOF 判斷。

5
1 1 1 2 2
3 1 2 2 2

輸出

輸出移動步驟時，需按照 ring x : y -> z 的格式，其中 x 為整數，y、z 為 a、b、c 其中一個。
最後在輸出最少步數。

ring 1 : a -> b
ring 2 : a -> c
ring 1 : b -> c
ring 3 : a -> b
ring 1 : c -> b
ring 2 : c -> a
ring 1 : b -> c
7

解題思路

參考 b190，這題稍微複雜了點，起始狀態和結束狀態都是亂的，不過其實沒甚麼差，因為起始狀態不管事有序或無序處理方式都是一樣的，所以只要把原本"奇數到 b 柱、偶數到 c 柱"改成"移動到指定的柱子"就行了，解決方法也很簡單，再額外開一個陣列紀錄目標位置即可。

其他的細節請參考本題的進階版 b592。

完整程式碼

AC (66ms, 120KB)
#include <stdio.h>

int n, count, tmp;
char now[25], end[25];

void dfs(int lv, char to)
{
    for (int i = lv; i; i--)
    {
        if (lv == n)
            to = end[i];
        if (now[i] != to)
        {
            dfs(i - 1, 294 - now[i] - to);
            printf("ring %d : %c -> %c\n", i, now[i], to);
            now[i] = to;
            count++;
        }
    }
}

int main()
{
    while (scanf(" %d", &n) == 1)
    {
        count = 0;
        for (int i = 1; i <= n; i++)
            scanf(" %d", &tmp), now[i] = tmp + 96;
        for (int i = 1; i <= n; i++)
            scanf(" %d", &tmp), end[i] = tmp + 96;
        dfs(n, 0);
        printf("%d\n", count);
    }
    return 0;
}
閱讀更多

a227: 三龍杯 -> 河內之塔

內容

河內之塔(Towers of Hanoi)是法國人 M.Claus(Lucas)於 1883 年從泰國帶至法國的，河內為越戰時北越的首都，即現在的胡志明市；1883 年法國數學家 Edouard Lucas 曾提及這個故事，據說創世紀時 Benares 有一座波羅教塔，是由三支鑽石棒（Pag）所支撐，開始時神在第一根棒上放置 64 個由上至下依由小至大排列的金盤（Disc），並命令僧侶將所有的金盤從第一根石棒移至第三根石棒，且搬運過程中遵守大盤子在小盤子之下的原則，若每日僅搬一個盤子，則當盤子全數搬運完畢之時，此塔將毀損，而也就是世界末日來臨之時。

img1

A            B          C

輸入

每行有一個正整數 N N <= 15

1
2
3

輸出

請輸出把 A 上 N 個環移動到 C 的方法

( 剛開始 A 層最下方的 Ring 編號為 N 最上方的編號為 1 )

Move ring 1 from A to C

Move ring 1 from A to B
Move ring 2 from A to C
Move ring 1 from B to C

Move ring 1 from A to C
Move ring 2 from A to B
Move ring 1 from C to B
Move ring 3 from A to C
Move ring 1 from B to A
Move ring 2 from B to C
Move ring 1 from A to C

解題思路

參考 b190，這題更簡單，不用把奇偶分配在不同的柱子上，直接全部丟到 C 柱即可。

完整程式碼

AC (20ms, 108KB)
#include <stdio.h>

int n;
char list[100];

void dfs(int lv, char to)
{
    for (int i = lv; i; i--)
    {
        if (list[i] != to)
        {
            dfs(i - 1, 198 - list[i] - to);
            printf("Move ring %d from %c to %c\n", i, list[i], to);
            list[i] = to;
        }
    }
}

int main()
{
    while (scanf(" %d", &n) == 1)
    {
        for (int i = 1; i <= n; i++)
            list[i] = 'A';
        dfs(n, 'C');
        putchar('\n');
    }
    return 0;
}
閱讀更多

b190: 97七區資訊學科5(改編)

內容

一個必有偶數層的河內塔，有 a b c 三根柱子，假設所有的環原本在 a 柱上，請將奇數號的環移到 b 柱上，偶數號的環移到 c 柱上，大的環不能疊在小的環上，請輸出移動過程和最少步數。

河內塔的規則為：
有三根柱子 a、b、c。a 桿上有 N 個(N>1)穿孔圓盤，盤的尺寸由下到上依次變小。
要求按下列規則進行移動：

  1. 每次只能移動一個圓盤，
  2. 大盤不能疊在小盤上面。

輸入

每一組只有一個整數，代表有 n 個環。

4

輸出

輸出移動步驟時，需按照『ring x : y -> z’的格式，其中 x 為整數，y、z 為 a、b、c 其中一個。
最後在輸出最少步數。

ring 1 : a -> b
ring 2 : a -> c
ring 1 : b -> c
ring 3 : a -> b
ring 1 : c -> a
ring 2 : c -> b
ring 1 : a -> b
ring 4 : a -> c
ring 1 : b -> a
ring 2 : b -> c
ring 1 : a -> b
共移動了 11 步

解題思路

先觀察一個高度為 3 的河內塔正確移動的順序

要將第 3 盤從 a 柱移動到 b 柱但第 2 盤擋住了

要將第 2 盤從 a 柱移動到 c 柱但第 1 盤擋住了

將第 1 盤從 a 柱移動到 b 柱避面擋到第 2 盤移動

第 1 盤移開了，將第 2 盤從 a 柱移動到 c 柱

第 2 盤移開了，但又被移動到 b 柱的第 1 盤擋住了

將第 1 盤從 b 柱移動到 c 柱避面擋到第 3 盤移動

第 1 盤移開了，將第 3 盤從 a 柱移動到 b 柱 (第 3 盤移動完成)
第 2 盤經過剛才的移動剛好也在 c 柱上，不用動 (第 2 盤移動完成)
第 1 盤還在 c 柱，將他移到 b 柱 (第 1 盤移動完成)

可以發現如果要將某盤從 a 柱移到 b 柱，就必須將該盤上面的所有盤子移動到不是 a 或 b 的 c 柱，也就是說從最底層那盤為奇數盤，就以將他移動到 b 柱為目標，將它上面的盤子移動到 c 柱，等他移動到 b 柱後再移動上面那盤至 c 柱，如此循環直到全部的盤子都分配至正確的位置即可。

所以實際上就是用遞迴完成以下循環，直到要沒有要移動的盤子後結束

把要移動的盤子上面的盤子都移動到不相干的柱子上 → 移動要移動的盤子 → 把要移動的盤子變成他上面那個 → 回到開始

一些其他的細節請參考 b592

完整程式碼

AC (7ms, 92KB)
#include <stdio.h>

int n, count;
char list[100];

void dfs(int lv, char to)
{
    for (int i = lv; i; i--)
    {
        if (lv == n)
            to = i & 1 ? 'b' : 'c';
        if (list[i] != to)
        {
            dfs(i - 1, 294 - list[i] - to);
            printf("ring %d : %c -> %c\n", i, list[i], to);
            list[i] = to;
            count++;
        }
    }
}

int main()
{
    while (scanf(" %d", &n) == 1)
    {
        count = 0;
        for (int i = 1; i <= n; i++)
            list[i] = 'a';
        dfs(n, '?');
        printf("共移動了 %d 步\n", count);
    }
    return 0;
}
閱讀更多

a863: 3. Happy Numbers

內容

大多數的人認為數字是冷酷無情的，事實上某些數字是充滿活力的，學會判斷一個數是否快樂其實很簡單。挑選一個正整數，求其所有位數平方的總和，持序這個動作直到所有位數的平方和為 1 或是進入循環，可以收斂到 1 則為快樂的，循環則為不快樂。可以假定所有循環週期不超過 100。

例如：
以 32 為例
32 → 33+22=13
13 → 11+33=10
10 → 11+00=1
故 32 是快樂的數

輸入

輸入包含一個正整數 n

32
4565

輸出

輸出”n is a happy number” 或”n is an unhappy number”(不含引號)

32 is a happy number
4565 is an unhappy number

解題思路

img1

參考上圖，任何無法收斂到 1 ，也就是"非"快樂數都會進入以下循環

4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4

而由於不管是從哪一點進入循環，只要不斷的求出該數的所有位數平方的總和，最後都會變成 4 ，所以只要判斷是否收斂到 1 (快樂數) 或是出現 4 (進入循環，非快樂數) 即可確認狀態跳出迴圈後輸出答案即可。

完整程式碼

AC (2ms, 92KB)
#include <stdio.h>

int main()
{
    int n, now, tmp;
    while (scanf(" %d", &n) == 1)
    {
        for (now = n; now != 1 && now != 4; now = tmp)
        {
            tmp = 0;
            while (now)
            {
                tmp += (now % 10) * (now % 10);
                now /= 10;
            }
        }
        if (now == 1)
            printf("%d is a happy number\n", n);
        else if (now == 4)
            printf("%d is an unhappy number\n", n);
    }
    return 0;
}
閱讀更多

a790: 12. Haunted House Inspector

內容

每當到了萬聖節，消防隊都會檢查迷宮鬼屋，確認有沒有著火和消防管夠不夠長、能不能撲滅所有的火。為了將這個程序自動化，你自告奮勇的寫一個程式來模擬。

輸入

輸入多組測資，每組第一行包含三個數字，分別代表地圖的長、寬以及消防管的長度。接著輸入迷宮地圖(一個字元代表一呎)，”#”代表牆壁、”S”代表迷宮入口、”F”代表找火位置，請你從入口進入沿著迷宮滅火直到消防管不夠長，迷宮轉角一定是垂直的，而且消防管碰到才能滅火。

60 9 84
#############S##############################################
#FFFFFF FF        #FFF           #       #   #FF    #  FFFF#
############### # #### ####### # #### #### ######## ######F#
# F F  FFFFF FFF#  FF#       # # #FFFF   #  F#      #FFFFFF#
##########F#### # ############ # ####### # ### ######F######
#               #  FFFFFFF   # # #FFFF   #  F#      #FFFFFF#
##########F####F# ############ # ####### # ### ###########F#
#  FFF  FFFFF       FFFFFFFF   #                     FFFFFF#
############################################################

輸出

請輸出滅火後地圖，以”.”代表消防管能到達的位置，如果火勢全部被撲滅，請再隔一行輸出“All Fires Extinguished!”( 不含引號 )。

#############.##############################################
#.................#..............#.......#...#......#  ....#
###############.#.####.#######.#.####.####.########.######.#
#...............#....#.......#.#.#.......#...#......#......#
##########.####.#.############.#.#######.#.###.######.######
#...............#............#.#.#.......#...#......#......#
##########.####.#.############.#.#######.#.###.###########.#
#..............................#...........................#
############################################################

All Fires Extinguished!

解題思路

題目的意思是將管線拉到最長後能滅掉的火全部滅掉，然後輸出滅完火後的地圖。

用 Dijkstra 演算法找出有限距離所能達到的全部位置，並將能達到位置的元素改為'.'全部找到後輸出滅完火的地圖，並判斷是否還有火('F')存在於地圖上，沒有的話再額外輸出"All Fires Extinguished!"表示火滅乾淨了即可。

完整程式碼

AC (2ms, 92KB)
#include <stdio.h>
#define MAX 110

int dp[MAX][MAX], row, col, len, sX, sY;
char map[MAX][MAX], * st;

char* strchr(const char ch)
{
    for (int i = 0; i < row; i++)
    {
        for (int j = 0; j < col; j++)
        {
            if (map[i][j] == ch)
                return &map[i][j];
        }
    }
    return NULL;
}

int main()
{
    while (scanf(" %d %d %d", &col, &row, &len) == 3)
    {
        getchar();
        for (int i = 0; i < row; i++)
        {
            gets(map[i]);
            for (int j = 0; j < col; j++)
                dp[i][j] = 0;
        }
        st = strchr('S');
        sX = (st - &map[0][0]) / MAX, sY = (st - &map[0][0]) % MAX;
        map[sX][sY] = '.', dp[sX][sY] = len - 1;
        while (--len)
        {
            for (int i = 0; i < row; i++)
            {
                for (int j = 0; j < col; j++)
                {
                    if (dp[i][j] == len)
                    {
                        if (i + 1 < row && map[i + 1][j] != '#')
                            map[i + 1][j] = '.', dp[i + 1][j] = len - 1;
                        if (i - 1 >= 0 && map[i - 1][j] != '#')
                            map[i - 1][j] = '.', dp[i - 1][j] = len - 1;
                        if (j + 1 < col && map[i][j + 1] != '#')
                            map[i][j + 1] = '.', dp[i][j + 1] = len - 1;
                        if (j - 1 >= 0 && map[i][j - 1] != '#')
                            map[i][j - 1] = '.', dp[i][j - 1] = len - 1;
                    }
                }
            }
        }
        for (int i = 0; i < row; i++)
            puts(map[i]);
        if (!strchr('F'))
            puts("All Fires Extinguished!");
    }
    return 0;
}
閱讀更多
1234…27