ABC075 B-Minesweeper グリッド
ABC075 B-Minesweeper
C++のグリッド問題を初めて真面目にやりました。
問題は以下。
実行時間制限: 2 sec / メモリ制限: 256 MB
配点 : 200 点
問題文H×W のマス目が与えられます。 入力において、全てのマスは文字で表されており、.は空きマス、 # は爆弾マスに対応します。 マス目は H 個の文字列 S1,...,SH で表されます。 文字列 Si の j 文字目は、マス目の上から i 番目、左から j 番目のマスに対応します。(1≦i≦H,1≦j≦W)イルカは各空きマスの上下左右および斜めの 8 方向で隣接しているマスに爆弾マスが何個あるか気になっています。 そこで、各空きマスに対応する . を、その空きマスの周囲8方向に隣接するマスにおける爆弾マスの個数を表す数字で置き換えることにしました。
以上の規則で置き換えられた後のマス目を出力してください。
制約1≦H,W≦50
Si は # と . からなる長さ W の文字列
〜考え方〜
高々50^2なので全探索。
グリッドの問題では、vector
周囲8方向はdxとdyをそれぞれ-1,0,1の二重ループをまわす。
dx = dy = 0のときは移動しないが、'.'の周りをみているので、それをカウントする心配はない。
コードは以下。
#include <bits/stdc++.h> using namespace std; #define rep(i,N) for(int i=0;i<int(N);++i) int main() { int H,W; cin>>H>>W; vector<string> S(H); rep(i,H)cin>>S[i]; rep(i,H)rep(j,W){ if(S[i][j] == '.'){ S[i][j]='0'; for (int dx = -1; dx <= 1; ++dx){ for (int dy = -1; dy <= 1; ++dy){ int nx = i+dx,ny = j+dy; if(0<=nx&&nx<H&&0<=ny&&ny<W){ if(S[nx][ny]=='#')S[i][j]++; } } } } } rep(i,H)cout<<S[i]<<endl; }