10189 Minesweeper

題目連結

題目敘述

你玩過「踩地雷（Minesweeper）」這款小遊戲嗎？這是一款出現在某個作業系統裡的小遊戲（我們一時想不起來是什麼作業系統）
遊戲的目標是在一個 M × N 的格子地圖中，找出所有地雷的位置。為了幫助你，遊戲會在安全格子中顯示一個數字，表示 這個格子周圍（最多 8 個相鄰格子）有多少顆地雷

舉例

假設你有下面這個 4 × 4 的地圖，其中 * 表示地雷， . 表示安全格子：

*........*......

那麼轉換後的地圖應該是這樣：

*100 2210 1 * 10 1110

如上所示，每個安全格子上的數字，就是它周圍八個格子裡地雷的數量（橫、直、斜都算）

輸入說明

輸入包含多個地圖，每張地圖格式如下：
第一行：
n m

• n是地圖的行數， m 是地圖的列數（保證 0 < n, m ≤ 100）
  接下來 n 行，每行剛好 m 個字元，只會包含：
• * 表示地雷
• . 表示安全格子
  當讀到 n = 0 且 m = 0 時，表示輸入結束，這一行不需處理

輸出說明

對每張地圖，輸出格式如下：

Field #x : 地圖結果

其中：

• x 是地圖的編號（從 1 開始編號）
• 原本是 '.' 的格子，要換成周圍地雷數量（0~8）
• 原本是 '*' 的格子維持不變
• 每張地圖輸出後，要空一行，但最後一張輸出後不要再多印空行

解題思路

1. 定義方向陣列
2. 讀取地圖
3. 讀取地圖並先把 . 換成 '0'
4. 計算每個非地雷格子的周圍地雷數
5. 輸出地圖

程式碼

#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
int dir[8][2] = {{1, 0}, {-1, 0}, {0, 1},  {0, -1},
                 {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
int main() {
  int n, m, field = 0;
  while (cin >> n >> m && n && m) {
    if (field) cout << endl;
    vector<string> vc(n);
    for (int i = 0; i < n; i++) {
      cin >> vc[i];
      for (int j = 0; j < m; j++) {
        if (vc[i][j] == '.') vc[i][j] = '0';
      }
    }
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        pair<int, int> p = {i, j};  // 現在座標
        if (vc[p.f][p.s] == '0') {
          for (int k = 0; k < 8; k++) {
            pair<int, int> now = {p.f + dir[k][0],
                                  p.s + dir[k][1]};  // 周圍8個座標
            /*
            . . .
            . x .
            . . .
            */
            if (0 <= now.f && now.f < n && 0 <= now.s &&
                now.s < m) {  // 如果在界內
              if (vc[now.f][now.s] == '*') {
                vc[p.f][p.s] += 1;
              }
            }
          }
        }
      }
    }
    // 輸出
    cout << "Field #" << ++field << ":" << endl;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        cout << vc[i][j];
      }
      cout << endl;
    }
    //
  }
  return 0;
}