a790: 12. Haunted House Inspector

2019-09-07

內容

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

輸入

輸入多組測資，每組第一行包含三個數字，分別代表地圖的長、寬以及消防管的長度。接著輸入迷宮地圖(一個字元代表一呎)，”#”代表牆壁、”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;
}