UVa11953 - Battleships(DFS)

題目大意

大家有玩過 Battleships game 嗎? 用兩張紙畫，目標是要擊沉對手的所有船艦，每一艘船艦都是 1 * N 大小的，要全部都被擊中就算輸了

題目是給你一張圖，請你判斷還有哪些戰艦還沒有被擊沉，被擊中並不包含擊沉

題目連結

重點觀念

• 理解英文題目
• DFS 應用

分析

這題不難，學會 DFS 後，只要碰到非 ‘.’ 的格子，就進行 DFS 只要 DFS 中有遇到 ‘x’ 就表示這艘船還沒有被完全擊沉就加一

心得

簡單，開始慢慢學會，也慢慢改變自己的程式碼風格，使其更好閱讀

題目程式碼

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

#include <iostream>
#include <bits/stdc++.h>
#define MAXN 120
#define LOCAL
using namespace std;
int T, N, kase = 0; //kase 輸出第幾個測資
char graph[MAXN][MAXN]; //題目的地圖
string s; //輸入題目資料用

int dfs(int x, int y){ //搜尋 DFS，判斷這區塊有沒有還存活的戰艦
    if(x < 0 || y < 0 || x >= N || y >= N) return 0; //超出邊界
    if(graph[x][y] == '.') return 0; //碰到海洋
    int cnt = 0; //表示還有幾個地方沒有被擊中
    if(graph[x][y] == 'x') cnt += 1; //表示這地方沒有被擊中
    graph[x][y] = '.'; //算過因此，表示為海洋
    cnt += dfs(x-1, y); //四個方向
    cnt += dfs(x+1, y);
    cnt += dfs(x, y-1);
    cnt += dfs(x, y+1);
    return cnt; //回傳有幾個地方還沒被擊中
}

void debug(){ //debug 用
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++) cout << graph[i][j] << ' ';
        cout << '\n';
    }
}

int main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif // LOCAL
    cin >> T;
    while(T--){
        cin >> N;
        for(int i = 0; i < N; i++){ //輸入資輛
            cin >> s;
            for(int j = 0; j < N; j++) graph[i][j] = s[j];
            //注意這裡的 s[j]，不是 s[i]
        }

        int ans = 0; //幾艘還在
        for(int i = 0; i < N; i++){ //遍地搜尋
            for(int j = 0; j < N; j++){
                if(graph[i][j] != '.'){
                    if(dfs(i, j) != 0) ans++; //如果 != 0 就表示還有地方沒有被擊中，因此戰艦+1
                }
            }
        }
        cout << "Case " << ++kase << ": "; //輸出答案
        cout << ans << '\n';
    }

    return 0;
}