AtCoder Minesweeperをvector無しで解いた


# はじめに
競プロをC++で書きたくなったので、C++入門を始めました。

https://atcoder.jp/contests/apg4b

[文字列と文字](
https://atcoder.jp/contests/apg4b/tasks/APG4b_m)の章で、[Minsweeper](https://atcoder.jp/contests/abc075/tasks/abc075_b)というB問題が文字列の知識だけでとけると書いてあります。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2261812/46d0c7da-c526-15fd-8fc7-06c8507f1b64.png)

面白いと思ったので、vectorなし縛りでこの問題を解いてみました。備忘録として残しておきます。


# コード

https://atcoder.jp/contests/abc075/tasks/abc075_b

```c++:minesweeper.cpp
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)

char ret_added_char(char s){
  if(s == '#'){return '#';}
  if(s == '.'){return '1';}
  if(s == '1'){return '2';}
  if(s == '2'){return '3';}
  if(s == '3'){return '4';}
  if(s == '4'){return '5';}
  if(s == '5'){return '6';}
  if(s == '6'){return '7';}
  if(s == '7'){return '8';}
  else{
    return '8';
  }
}

int main() {
  int H, W;
  cin >> H >> W ;
  string S;
  string cell = "";

  rep(i, H){
    cin >> S;
    cell += S;
  }

  rep(i, cell.size()){
    if (cell.at(i) == '#'){
      // left up, up, right up
      // it is not occurred that over string.size() because of up 
      if ((i - W - 1) >= 0 && i % W != 0){cell.at(i - W - 1) = ret_added_char(cell.at(i - W - 1));}
      if ((i - W) >= 0){cell.at(i - W) = ret_added_char(cell.at(i - W));}
      if ((i - W + 1) >= 0 && (i - W + 1) % W != 0){cell.at(i - W + 1) = ret_added_char(cell.at(i - W + 1));}

      // left, right
      if (i % W != 0 && (i - 1) >= 0){cell.at(i - 1) = ret_added_char(cell.at(i - 1));}
      if ((i - W + 1) % W != 0 && (i + 1) < cell.size()){cell.at(i + 1) = ret_added_char(cell.at(i + 1));}

      // left down, down, right down
      if ((i + W - 1) < cell.size() && i % W != 0){cell.at(i + W - 1) = ret_added_char(cell.at(i + W - 1));}
      if ((i + W) < cell.size()){cell.at(i + W) = ret_added_char(cell.at(i + W));}
      if ((i + W + 1) < cell.size() && (i + W + 1) % W != 0){cell.at(i + W + 1) = ret_added_char(cell.at(i + W + 1));}
    } 
  }

  rep(i, cell.size()){
    if (cell.at(i) == '.'){
      cout << '0';
    }
    else{
      cout << cell.at(i);
    }

    if (i % W == W - 1){
      cout << endl;
    }
  }

  return 0;
}

```

# 問題文
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2261812/86c4f724-1027-1c83-ee41-756e88625732.png)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2261812/7b3963d5-c314-c05e-a28f-c4947dbe4138.png)


# 解法
この問題は、```.```(空マス)に隣接する```#```(爆弾マス)の数を```.```空マスに入れて出力する問題です。

## 入力
まず、数値の受け取り方について考えます。今回はvectorを使用しないので、全て文字列として受け取ります。そして、入力を連結して```string cell```に格納します。
```c++:minesweeper.cpp
.
.

int main() {
  int H, W;
  cin >> H >> W ;
  string S;
  string cell = "";

  rep(i, H){
    cin >> S;
    cell += S;
  }
.
.
.
```
## 隣接するマスの表し方

入力例1を手書きで書くとこのようになります。今回はvectorを使用しないので**添え字が0~要素数**までの連番になっていることに注意してください。


<img src = "https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2261812/655a8503-d618-69ab-c6a2-1c40d11e42ed.png" width = 50%>


マス目は以下の規則で表せます。iが現在いる番号で```#```の爆弾マスになっています。入力例の番号6を見ると分かりやすいです。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2261812/033711ef-d19f-5f09-e285-fb4ed2a14405.png" width=60%>


以上を踏まえると、この問題は、ループ中のi番目の文字列に```#```(爆弾マス)があった場合、上記のような周囲のマスに1を加えれば解けるということになります。

## 下準備(文字列を加算する関数の実装)

上記より、周囲のマスに+1する処理が必要になります。しかし、char型に+1をしても計算できません。そのため、文字列加算用の関数を作成します。

だいぶ力技ですが、8までなので何とかなります。


```c++
char ret_added_char(char s){
  if(s == '#'){return '#';}
  if(s == '.'){return '1';}
  if(s == '1'){return '2';}
  if(s == '2'){return '3';}
  if(s == '3'){return '4';}
  if(s == '4'){return '5';}
  if(s == '5'){return '6';}
  if(s == '6'){return '7';}
  if(s == '7'){return '8';}
  else{
    return '8';
  }
}

```


まとめると
- ```#```(爆弾マス)は何もしない
- char型で数字を受け取ったら、+1した値をchar型で返す
- 周囲に爆弾がある数は最大8なので、1~8に収まらない場合は8を返す


## 周囲8マスへの加算処理
ここがメインになります。

これを手元に書くと分かりやすいです。
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2261812/f4ed8d2a-053b-d0ef-2e4c-aab3c182b882.png" width=50%>

```c++
  rep(i, cell.size()){
    if (cell.at(i) == '#'){
      // left up, up, right up
      // it is not occurred that over string.size() because of up 
      if ((i - W - 1) >= 0 && i % W != 0){cell.at(i - W - 1) = ret_added_char(cell.at(i - W - 1));}
      if ((i - W) >= 0){cell.at(i - W) = ret_added_char(cell.at(i - W));}
      if ((i - W + 1) >= 0 && (i - W + 1) % W != 0){cell.at(i - W + 1) = ret_added_char(cell.at(i - W + 1));}

      // left, right
      if (i % W != 0 && (i - 1) >= 0){cell.at(i - 1) = ret_added_char(cell.at(i - 1));}
      if ((i - W + 1) % W != 0 && (i + 1) < cell.size()){cell.at(i + 1) = ret_added_char(cell.at(i + 1));}

      // left down, down, right down
      if ((i + W - 1) < cell.size() && i % W != 0){cell.at(i + W - 1) = ret_added_char(cell.at(i + W - 1));}
      if ((i + W) < cell.size()){cell.at(i + W) = ret_added_char(cell.at(i + W));}
      if ((i + W + 1) < cell.size() && (i + W + 1) % W != 0){cell.at(i + W + 1) = ret_added_char(cell.at(i + W + 1));}
    } 
  }
```

### 共通の処理
- iから、cell.size()までループを回す

- ```cell.at(i) == #```のとき、周辺のマスに1を加算する
- 上記は```cell.at(マスの位置)```に```ret_add_char```関数を代入することで行われる

```c++: 例
cell.at(i-W-1)=ret_added_char(cell.at(i-W-1));
```

### 左上、上、右上のマス目に加算する処理
```c++:
// left up,up right up 
if ((i - W - 1) >= 0 && i % W != 0){cell.at(i - W - 1) = ret_added_char(cell.at(i - W - 1));}
if ((i - W) >= 0){cell.at(i - W) = ret_added_char(cell.at(i - W));}
if ((i - W + 1) >= 0 && (i - W + 1) % W != 0){cell.at(i - W + 1) = ret_added_char(cell.at(i - W + 1));}

```

#### 場合分け
左上、上、右上に共通して、添え字が0を下回ってしまう可能性があります。そのため、0以上の場合のみ処理を行うようにします。(ex,i=0)

**上の場合**
上に行けないのは、0を下回るときのみです。

**左上の場合**
左上に行けない場所があります。要素の左端に```#```があるときです。要素の左端は式で表すと
```i%W == 0```
になります。
例えば、0~14のうち、左端の```0,5,10```のみがW=5で割り切れます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2261812/a077d6fb-5379-9547-b6ad-a5f4e0b3c696.png" width=50%>

**右上の場合**
右上に行けない場所があります。要素の右端に```#```があるときです。要素の右端は式で表すと
```(i-W+1)%W == 0```
になります。

<img src = "https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2261812/5fd89e08-e302-b93c-47d3-4694d9000095.png" width=50%>


右端のiからW+1を引いた数は左端になります。(ex, 4-5+1=0, 9-5+1 = 5,)
先ほどのように、左端はWで割り切れるので```(i-W+1)%W == 0```の場合には処理しないようにします。

ここまでくると、ほぼ終わったようなものです。

### 左、右のマス目のマス目に加算する処理
```c++:
// left,right
if (i % W != 0 && (i - 1) >= 0){cell.at(i - 1) = ret_added_char(cell.at(i - 1));}
if ((i - W + 1) % W != 0 && (i + 1) < cell.size()){cell.at(i + 1) = ret_added_char(cell.at(i + 1));}
```

#### 場合分け
**左の場合**
- 要素が0を下回る可能性があります、そのため ```(i-1)>=0```
- 左端だと左側に1加算できないので、先ほどのように左端```i%W==0```の時は処理をしないようにします

**右の場合**
- 要素がcell.size()を上回る可能性があります、そのため```(i+1)<cell.size()```
- 右端だと右側に1加算できないので、先ほどのように右端```(i-W+1)%W == 0```の時は処理しないようにします。


### 左下、下、右下のマス目に加算する処理
```c++:
// left down, down, right down
if ((i + W - 1) < cell.size() && i % W != 0){cell.at(i + W - 1) = ret_added_char(cell.at(i + W - 1));}
if ((i + W) < cell.size()){cell.at(i + W) = ret_added_char(cell.at(i + W));}
if ((i + W + 1) < cell.size() && (i + W + 1) % W != 0){cell.at(i + W + 1) = ret_added_char(cell.at(i + W + 1));}
```

#### 場合分け
**下の場合**
- 要素がcell.size()を上回る可能性があります、そのため```(i+W) < cell.size()```

**左下の場合**
- 要素がcell.size()を上回る可能性があります、そのため```(i+W-1) < cell.size()```
- 左端だと左下に1加算できないので、先ほどのように左端```i%W==0```の時は処理をしないようにします

**右の場合**
- 要素がcell.size()を上回る可能性があります、そのため```(i+1)<cell.size()```
- 右端だと右下に1加算できないので、先ほどのように右端```(i+W+1)%W == 0```の時は処理しないようにします。


## 出力
```c++:
  rep(i,cell.size()){
    if(cell.at(i) == '.')
      cout << '0' ;
    else 
      cout << cell.at(i);
    
    if(i%W == W-1)
      cout << endl;
  }

```
- 周りに爆弾マスがないときには```.```のままになるので、ここで0にします。
- ```i%w == W-1```になるのは各行の右端だけですので、ここで改行します。

# ACしたコード（再掲）

```c++:minesweeper.cpp
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)

char ret_added_char(char s){
  if(s == '#'){return '#';}
  if(s == '.'){return '1';}
  if(s == '1'){return '2';}
  if(s == '2'){return '3';}
  if(s == '3'){return '4';}
  if(s == '4'){return '5';}
  if(s == '5'){return '6';}
  if(s == '6'){return '7';}
  if(s == '7'){return '8';}
  else{
    return '8';
  }
}

int main() {
  int H, W;
  cin >> H >> W ;
  string S;
  string cell = "";

  rep(i, H){
    cin >> S;
    cell += S;
  }

  rep(i, cell.size()){
    if (cell.at(i) == '#'){
      // left up, up, right up
      // it is not occurred that over string.size() because of up 
      if ((i - W - 1) >= 0 && i % W != 0){cell.at(i - W - 1) = ret_added_char(cell.at(i - W - 1));}
      if ((i - W) >= 0){cell.at(i - W) = ret_added_char(cell.at(i - W));}
      if ((i - W + 1) >= 0 && (i - W + 1) % W != 0){cell.at(i - W + 1) = ret_added_char(cell.at(i - W + 1));}

      // left, right
      if (i % W != 0 && (i - 1) >= 0){cell.at(i - 1) = ret_added_char(cell.at(i - 1));}
      if ((i - W + 1) % W != 0 && (i + 1) < cell.size()){cell.at(i + 1) = ret_added_char(cell.at(i + 1));}

      // left down, down, right down
      if ((i + W - 1) < cell.size() && i % W != 0){cell.at(i + W - 1) = ret_added_char(cell.at(i + W - 1));}
      if ((i + W) < cell.size()){cell.at(i + W) = ret_added_char(cell.at(i + W));}
      if ((i + W + 1) < cell.size() && (i + W + 1) % W != 0){cell.at(i + W + 1) = ret_added_char(cell.at(i + W + 1));}
    } 
  }

  rep(i, cell.size()){
    if (cell.at(i) == '.'){
      cout << '0';
    }
    else{
      cout << cell.at(i);
    }

    if (i % W == W - 1){
      cout << endl;
    }
  }

  return 0;
}

```


# 最後に
面白い問題でした。絶対にVectorを使用するべきです。