ABC075 B - Minesweeper - ペンギンかっこいい

備忘録

問題

回答 1

"use strict"
 
function Main(input) {
  input = input.trim().split('\n');
  const H = input[0].trim().split(' ').map(Number)[0];
  const W = input[0].trim().split(' ').map(Number)[1];
  const S = input.slice(1, H+1).map(val => val.trim().split(''));
 
  for(let h=0; h<H; h++){
    for(let w=0; w<W; w++){
      let tmp = S[h][w];
      if(tmp === '#'){
        if (h > 0) {
          if(w > 0) S[h-1][w-1] = S[h-1][w-1] === '.' ? 1 : S[h-1][w-1] === '#' ? '#' : S[h-1][w-1] + 1;
          S[h-1][w]   = S[h-1][w] === '.' ? 1 : S[h-1][w] === '#' ? '#' : S[h-1][w] + 1;
          if(w < W - 1) S[h-1][w+1] = S[h-1][w+1] === '.' ? 1 : S[h-1][w+1] === '#' ? '#' : S[h-1][w+1] + 1;
        }
 
        if (w > 0) {
          S[h][w-1]   = S[h][w-1] === '.' ? 1 : S[h][w-1] === '#' ? '#' : S[h][w-1] + 1;
        }
 
        if (w < W - 1) {
          S[h][w+1]   = S[h][w+1] === '.' ? 1 : S[h][w+1] === '#' ? '#' : S[h][w+1] + 1;
        }
 
        if (h < H - 1) {
          if(w > 0) S[h+1][w-1] = S[h+1][w-1] === '.' ? 1 : S[h+1][w-1] === '#' ? '#' : S[h+1][w-1] + 1;
          S[h+1][w]   = S[h+1][w] === '.' ? 1 : S[h+1][w] === '#' ? '#' : S[h+1][w] + 1;
          if(w < W - 1) S[h+1][w+1] = S[h+1][w+1] === '.' ? 1 : S[h+1][w+1] === '#' ? '#' : S[h+1][w+1] + 1;
        }
      }
    };
  };
 
  console.log(S.join('\n').replace(/,/g, '').replace(/\./g, '0'));
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

考え方

爆弾マスをS、位置を[h][w]とするとき、
周囲の8マスはS[h-1][w-1], S[h-1][w], S[h-1][w+1], S[h][w-1], S[h][w+1], S[h+1][w-1], S[h+1][w], S[h+1][w+1]となる。
これらをすべて探索し、指定範囲内かつ爆弾(#)でない場合には+1することで回答を求めることができる。
爆弾を対象とし、全ての条件を漏れの内容に実装することで答えを導く回答。

回答 2

"use strict"
 
function Main(input) {
  input = input.trim().split('\n');
  const H = input[0].trim().split(' ').map(Number)[0];
  const W = input[0].trim().split(' ').map(Number)[1];
  const S = input.slice(1).map(val => val.trim().split(''));
  const dh = [-1, -1, -1, 0, 0, 1, 1, 1];
  const dw = [-1, 0, 1, -1, 1, -1, 0, 1];
 
  // 全てのS[h][w]のパターンを探索
  for (let h=0; h<H; h++) {
    for (let w=0; w<W; w++) {
      // 対象が爆弾(#)の場合、スキップ
      if (S[h][w] === '#') continue;
 
      // 対象から移動範囲の8マスを探索
      let cnt = 0;
      for (let d=0; d<8; d++) {
        let nh = h + dh[d];
        let nw = w + dw[d];
        
        if (nh >= 0 && nh < H && nw >= 0 && nw < W) {
          // 移動範囲が指定された範囲から外に出ていない場合、
          // 対象の移動範囲8マス内に爆弾(#)があるか否かを探索。
          // 爆弾が存在する場合、cnt(自身の周囲に爆弾数)を+1する。
          let t = S[nh][nw];
          if (t === '#') cnt += 1;
        };
      };
 
      // 対象をcnt(自身の周囲に爆弾数)に置き換える
      S[h][w] = cnt;
    };
  };
 
  console.log(S.map(s => s.join('')).join('\n'));
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

考え方

空きマスを対象として、その周囲8マスの爆弾数をカウントする解法。
初めに移動しうる範囲を宣言する。

  const dh = [-1, -1, -1, 0, 0, 1, 1, 1];
  const dw = [-1, 0, 1, -1, 1, -1, 0, 1];

dhはh軸で取りうる範囲。dwはw軸で取りうる範囲になっているため、
S[dh[0], dw[0]]が左上、S[dh[1], dw[1]]が真上、S[dh[2], dw[2]]が右上...とfor(let d=0; d<8; d++)とすることで、
探索範囲を求めることが出来る。

探索範囲の8マスを求めた後、探索するマスが指定された範囲内かつ爆弾(`#')の場合をカウントしておくことで、
自身の周囲8マスに爆弾がいくつあるかを求めることができる。