LoginSignup
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 1 year has passed since last update.

@hwatahik(綿引)

AtCoder Minesweeperをvector無しで解いた

Last updated at Posted at 2023-06-17

はじめに

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

文字列と文字の章で、MinsweeperというB問題が文字列の知識だけでとけると書いてあります。
image.png

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

コード

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
image.png

解法

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

入力

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

minesweeper.cpp
.
.

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

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

隣接するマスの表し方

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

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

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

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

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

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

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マスへの加算処理

ここがメインになります。

これを手元に書くと分かりやすいです。

  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関数を代入することで行われる

例
cell.at(i-W-1)=ret_added_char(cell.at(i-W-1));

左上、上、右上のマス目に加算する処理

// 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で割り切れます。

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

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

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

左、右のマス目のマス目に加算する処理

// 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の時は処理しないようにします。

左下、下、右下のマス目に加算する処理

// 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の時は処理しないようにします。

出力

  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したコード（再掲）

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を使用するべきです。

1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?