UVa1103 - Ancient Messages(DFS)

題目大意

考古學家們給你一些古老文字，請你根據題目給你的資料進行判斷，這圖片有哪些文字，按照字母順序輸出，但你必須想辦法自己在古老文字中辨識古老文字。

題目給你的值是 16 位元的。
古老文字不會重疊、至少會有一個文字。

題目連結

重點觀念

• 能夠理解題目英文
• 能找出題目文字輸出的規律性
• 了解 DFS

分析：

難題，但不是難在該難的地方www，例如他要如何在題目資料中辨識文字呢，是按照文字中有幾個空白區段來辨識的…，沒有看別人的 blog 真的不會懂…，甚麼爛題目..。

特別還給他 16 位元來混淆大家的想法，這題真夠狠的，我都被他騙了 2 hr 的時間。

基本只有一個空格的是 W、兩個空格的是 A、三個空格是 K，以此類推 “WAKJSD”，而判斷空格的方式就是先將 16 位元先拆開來看

區塊定義：被 1 包圍的所有的 0。

範例 A

00010
01101
00010
00000

這樣的話就是 A，因為在 (4,2) 的 0，被 1 給包圍，因此答案是 A。

範例 A-2

00110
01001
00110
00000

這樣的話就是 A，因為 (3,2) 跟 (4,2) 都是 0， 1 給包圍，因此答案還是 A。

範例 K

01111
01010
01111
00000

這樣的話就是 A，因為 (3,2) 跟 (5,2) 都是 0，但這兩個不是同個區塊，是被 1 分隔兩地，因此答案是，因此答案還是 K。

重新整理

因此我們可以知道，1 包圍很多 0 並且那些 0 都是不同的區塊時，越多區塊就是古老文字越多區塊的文字，像 D 就是有 6 個區塊，透過這樣推出。

沒有，這超難的…，在考大家聯想力..。

但現在我們可以知道了一件事，我們是要透過 1 包圍的區塊中判斷古老文字，因此我們先將 1 外圍的 0 全部都先表示成 2(有就是這些空格都是無意義，陪襯用)，接下來再判斷當我們走到 1 的使用開始搜尋外圍的 1 且當其中找到 0 時，就將那區塊全部都設為 2，表示已用過，並且記錄區塊，就可以判斷文字了！　

因此判斷的方式如下:

• 先寫一個 DFS 將外圍的 0 都消除
• 再來遍地搜尋 1，但找到 1 就開始進行 DFS
• 如果從第二點的 DFS 搜尋到 0，表示這裡有區塊
• 將那些區塊全部都設為 2，因為都是同個區塊，實作用 DFS
• 根據幾個區塊而輸出文字，這樣即可。

參考來源

我的朋友 - 陳立瑋

心得

這題真的很機車…，我想這題原本應該是給比賽用的才讓大家去猜測，但是我認為那個時候的大家應該也不知道吧…，這都快比 CF 的設計解題難 10 倍且還是難在非重要的地方，我認為很難過QQ，因為我就這樣被耍了兩個小時。

總之，訓練自己的英文能力很重要，雖然這題很機車，但是他也讓我大概理解影片解碼的方式了，謝謝他!

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

#include <bits/stdc++.h>
#define LOCAL
#define boardY 52 * 4 // y 邊界，因為題目是 16 進位，但是我們要把它拆成 2 進位，才能分隔區塊
using namespace std;
int W, H, kase=0, space;
int graph[202][boardY + 20]; //地圖
string word = "WAKJSD", ans, temp; // word[i] 有 i 個區塊的象形文字, ans 答案

void dfs_white(int h, int w){ //把當前空白區塊都掃描，用於一開始的去除外圍白色與去除 1 裡面的白色區塊
    if(h > H + 2|| w > boardY || h < 0 || w < 0) return; //到邊界就不在繼續
    if(graph[h][w] != 0) return; //此座標不是白色就不繼續
    graph[h][w] = 2; //視為已用過
    dfs_white(h + 1, w); //搜尋 4 個方向
    dfs_white(h - 1, w);
    dfs_white(h, w + 1);
    dfs_white(h, w - 1);
}

void dfs_black(int h, int w){ //沿著 1 搜尋，只要碰到 0 就表示裡面有區塊，跳至 dfs_white 將那區塊全部掃描
    if(h > H + 2 || w > boardY || h < 0 || w < 0) return; //到邊界就不在繼續
    if(graph[h][w] == 1){ //表示此座標是 1
        graph[h][w] = 2; //視為已用過
        dfs_black(h + 1, w); //搜尋 4 個方向繼續沿著 1 搜尋
        dfs_black(h - 1, w);
        dfs_black(h, w + 1);
        dfs_black(h, w - 1);
    }
    else if(graph[h][w] == 0){ //表示這邊有區塊
        space++; //區塊++
        //cout << "space is " << space << '\n';
        dfs_white(h, w); //將那區塊全部掃描一次
    }
    //cout << "dfs_black " << h << ' ' << w << '\n';
}

void debug(){ //debug 用
    for(int i = 1; i < H + 2; i++){
        for(int j = 5; j <= (W + 1) * 4; j++) cout << graph[i][j] << ' ';
        cout << '\n';
    }
}

int main(){
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif // LOCAL
    while(cin >> H >> W && H && W){ //輸入 H,W
        memset(graph, 0, sizeof(graph)); //重置，避免影響這次測資
        for(int i = 1; i <= H; i++){ //輸入資料
            cin >> temp;
            for(int j = 0; j < W; j++){
                if(isdigit(temp[j])) space = temp[j] - '0'; 
                //16 進位判斷，前 9 個數字都跟 10 進位相同
                else space = temp[j] - 'a' + 10; //將 16 進位轉成 10 進位
                for(int k = 0; k < 4; k++) graph[i][(j + 1) * 4 + 4 - k] = (int) 1 & (space >> k);
                //將 10 進位轉 2 進位，由於原本是 16 進位，因此最大只會有 4 個數字(位元)，
                // 1 & (space >> k) 則是判斷那個數字(位元)原本是 1 還是 0，由於只要判斷 1 位元，並不要把其他位元牽扯，因此 & 1。
            }
        }
        dfs_white(0, 0); //先將外圍的 0 先消除
        //debug();
        ans = ""; //答案清除
        for(int i = 0; i < 202; i++){ //掃描，找出 1
            for(int j = 0; j < boardY; j++){
                if(graph[i][j] == 1){ //找到 1
                    space = 0; //將區塊設為 0
                    dfs_black(i, j); //沿著 1 搜尋
                    ans += word[space]; //幾個區塊就輸出相對應的象形文字
                }
            }
        }
        sort(ans.begin(), ans.end()); //字典排序
        cout << "Case " << ++kase << ": "; //說明這是第幾個 case
        cout << ans << '\n';
    }
    return 0;
}