迷路 【幅優先探索・深さ優先探索メニュー 】

幅優先探索・深さ優先探索メニュー 【1 , 3, N マスの移動・ 壁のあるグリッドでの n マスの移動・ゴール判定・迷路 】

問題【STEP: 1】1 マスの移動
Task
グリッドのマス (y, x) から1マス移動して到達できるマスを ‘*’にしたグリッドを出力してね。

【1 マスの移動】コード 1/2

reader.on('close', () => {
   const [H, W] = lines.shift().split(' ').map(Number);  // H 行 W 列
   const [Y, X] = lines.shift().split(' ').map(Number);  // スタート
   const grid = [];  // グリッド
   for (let i = 0; i < H; i++) {
      grid.push(new Array(W).fill('.'));
   }
   grid[Y][X] = '*';
   if (X + 1 < W) {
      grid[Y][X + 1] = '*';
   }
   if (X - 1 >= 0) {
      grid[Y][X - 1] = '*';
   }
   if (Y + 1 < H) {
      grid[Y + 1][X] = '*';
   }
   if (Y - 1 >= 0) {
      grid[Y - 1][X] = '*';
   }
   grid.forEach(value => {
      console.log(value.join(''));
   });
});
hogeちゃんの画像

upしました。

top

【1 マスの移動】コード 2/2

reader.on('close', () => {
   const [H, W] = lines.shift().split(' ').map(Number);  // H 行 W 列
   const [Y, X] = lines.shift().split(' ').map(Number);  // スタート
   for (let y = 0; y < H; y++) {
      const grid = [];  // グリッド(一行)
      for (let x = 0; x < W; x++) {
         let reach = false;  // 移動可否の真偽値
         if (y === Y) {  // y が Y で…
            if (x === X - 1 || x === X + 1 || x === X) {  // x が X または X +- 1 なら…
               reach = true;  // 移動可
            }
         }
         if (x === X) {  // x が X で…
            if (y === Y - 1 || y === Y + 1 || y === Y) {  // y が Y または Y +- 1 なら…
               reach = true;  // 移動可
            }
         }
         reach ? grid.push('*') : grid.push('.');  // 移動可ならgrid[y][x]は'*' : 不可なら'.'
      }
      console.log(grid.join(''));
   }
});
hogeちゃんの画像

upしました。

top
問題【STEP: 2】3 マスの移動
Task
グリッドのマス (y, x) から3マス移動して到達できるマスを ‘*’にしたグリッドを出力してね。

【3 マスの移動】コード 1/2

reader.on('close', () => {
   const [H, W] = lines[0].split(' ').map(Number);  // H 行 W 列
   let [Y, X] = lines[1].split(' ').map(Number);  // スタート
   const grid = [];  // グリッド
   for (let h = 0; h < H; h++) {
      grid.push(new Array(W).fill('.'));
   }
   grid[Y][X] = '*';  // スタート地点は'*'
   for (let i = -1; i < 2; i++) {
      let x = X;
      x += i;
      for (let j = -1; j < 2; j++) {
         let y = Y;
         y += j;
         if (Math.abs(i) !== Math.abs(j) && x > -1 && x < W && y > -1 && y < H) {
            grid[y][x] = '*';
            [Y1, X1] = [y, x];
            for (let i = -1; i < 2; i++) {
               let x = X1;
               x += i;
               for (let j = -1; j < 2; j++) {
                  let y = Y1;
                  y += j;
                  if (Math.abs(i) !== Math.abs(j) && x > -1 && x < W && y > -1 && y < H) {
                     grid[y][x] = '*';
                     [Y2, X2] = [y, x];
                     for (let i = -1; i < 2; i++) {
                        let x = X2;
                        x += i;
                        for (let j = -1; j < 2; j++) {
                           let y = Y2;
                           y += j;
                           if (Math.abs(i) !== Math.abs(j) && x > -1 && x < W && y > -1 && y < H) {
                              grid[y][x] = '*';
                           }
                        }
                     }
                  }
               }
            }
         }
      }
   }
   grid.forEach(value => {
      console.log(value.join(''));
   });
});
hogeちゃんの画像

upしました。

top

【3 マスの移動】コード 2/2

reader.on('close', () => {
   const [H, W] = lines.shift().split(' ').map(Number);  // H 行 W 列
   const [Y, X] = lines.shift().split(' ').map(Number);  // スタート
   const Q = [];
   const grid = [];  // グリッド
   const len = [];
   for (let i = 0; i < H; i++) {
      grid.push(new Array(W).fill('.'));
      len.push(new Array(W).fill(-1));
   }
   grid[Y][X] = '*';
   len[Y][X] = 0;
   Q.push([Y, X]);
   while (Q.length) {
      const [ny, nx] = Q.shift();
      if (len[ny][nx] === 3) {
         continue;
      }
      for (let i = -1; i <= 1; i += 2) {
         if (0 <= ny + i && ny + i < H && grid[ny + i][nx] === '.') {
            Q.push([ny + i, nx]);
            len[ny + i][nx] = len[ny][nx] + 1;
            grid[ny + i][nx] = '*';
         }
         if (0 <= nx + i && nx + i < W && grid[ny][nx + i] == '.') {
            Q.push([ny, nx + i]);
            len[ny][nx + i] = len[ny][nx] + 1;
            grid[ny][nx + i] = '*';
         }
      }
   }
   for (const value of grid) {
      console.log(value.join(''));
   }
});
hogeちゃんの画像

upしました。

top
問題【STEP: 3】N マスの移動
Task
グリッドのマス (y, x) からNマス移動して到達できるマスを ‘*’にしたグリッドを出力してね。

【N マスの移動】コード

reader.on('close', () => {
   const BFS = (point, next, n) => {
      if (!point.length || n === 0) {
         return;
      }
      for (const p of point) {
         const [Y, X] = p;
         for (let i = -1; i <= 1; i += 2) {
            if (Y + i < H && Y + i >= 0 && grid[Y + i][X] === '.') {
               grid[Y + i][X] = '*';
               next.push([Y + i, X]);
            }
            if (X + i < W && X + i >= 0 && grid[Y][X + i] === '.') {
               grid[Y][X + i] = '*';
               next.push([Y, X + i]);
            }
         }
      }
      return BFS(next, [], n - 1);
   };
   const [H, W, N] = lines.shift().split(' ').map(Number);  // H 行 W 列 N 回移動
   const [Y, X] = lines.shift().split(' ').map(Number);  // スタート
   const Point = [
      [Y, X]
   ];
   const grid = [];  // グリッド
   for (let h = 0; h < H; h++) {
      grid.push(new Array(W).fill('.'));
   }
   grid[Y][X] = '*';
   BFS(Point, [], N);
   grid.forEach(row => {
      console.log(row.join(''));
   });
});
hogeちゃんの画像

upしました。

top
問題【STEP: 4】壁のあるグリッドでの n マスの移動
Task
壁ありのグリッドのマス (y, x) からNマス移動して到達できるマスを ‘*’にしたグリッドを出力してね。

【壁のあるグリッドでの n マスの移動】コード

reader.on('close', () => {
   const BFS = (point, next, n) => {
      if (!point.length || n === 0) {
         return;
      }
      for (const p of point) {
         const [y, x] = p;
         for (let i = -1; i <= 1; i += 2) {
            if (y + i < H && y + i >= 0 && grid[y + i][x] === '.') {
               grid[y + i][x] = '*';
               next.push([y + i, x]);
            }
            if (x + i < W && x + i >= 0 && grid[y][x + i] === '.') {
               grid[y][x + i] = '*';
               next.push([y, x + i]);
            }
         }
      }
      return BFS(next, [], n - 1);
   };
   const [H, W, N] = lines.shift().split(' ').map(Number);  // H 行 W 列 N 回移動
   const [Y, X] = lines.shift().split(' ').map(Number);  // スタート
   const Point = [
      [Y, X]
   ];
   const grid = [];  // グリッド
   for (let h = 0; h < H; h++) {
      grid.push(lines.shift().split(''));
   }
   grid[Y][X] = '*';
   BFS(Point, [], N);
   grid.forEach(row => {
      console.log(row.join(''));
   });
});
hogeちゃんの画像
upしました。
top
問題【STEP: 5】ゴール判定
Task
グリッドの情報とスタート地点, ゴール地点が与えられるのでゴールに到達できるか判定してね。

【ゴール判定】コード

reader.on('close', () => {
   const BFS = (point, next) => {
      if (!point.length) {
         return;
      }
      for (const p of point) {
         const [y, x] = p;
         for (let i = -1; i <= 1; i += 2) {
            if (y + i < H && y + i >= 0 && grid[y + i][x] === '.') {
               grid[y + i][x] = '*';
               next.push([y + i, x]);
            }
            if (x + i < W && x + i >= 0 && grid[y][x + i] === '.') {
               grid[y][x + i] = '*';
               next.push([y, x + i]);
            }
         }
      }
      return BFS(next, []);
   };
   const [H, W] = lines.shift().split(' ').map(Number);  // H 行 W 列
   const [sy, sx] = lines.shift().split(' ').map(Number);  // スタート
   const [gy, gx] = lines.shift().split(' ').map(Number);  // ゴール
   const Point = [[sy, sx]];  // 移動先(キュー)
   const grid = [];  // グリッド
   for (let h = 0; h < H; h++) {
      grid.push(lines.shift().split(''));
   }
   grid[sy][sx] = '*';
   BFS(Point, []);
   console.log(grid[gy][gx] === '*' ? 'Yes' : 'No');
});
hogeちゃんの画像

upしました。

top
問題【FINAL】迷路
Task
グリッドの情報が与えられるのでスタート地点からゴール地点まで何マスで到達できるか判定してね。

【迷路】コード

reader.on('close', () => {
   const BFS = (point, next, t) => {  // 幅優先探索
      if (!point.length || grid[gy][gx] === '*') {
         return t;
      }
      for (const p of point) {
         const [y, x] = p;
         for (let i = -1; i <= 1; i += 2) {
            if (y + i < H && y + i >= 0 && grid[y + i][x] === '.') {
               grid[y + i][x] = '*';
               next.push([y + i, x]);
            }
            if (x + i < W && x + i >= 0 && grid[y][x + i] === '.') {
               grid[y][x + i] = '*';
               next.push([y, x + i]);
            }
         }
      }
      return BFS(next, [], t + 1);
   };
   const [H, W] = lines.shift().split(' ').map(Number);  // H 行 W 列
   const [sy, sx] = lines.shift().split(' ').map(Number);  // スタート
   const [gy, gx] = lines.shift().split(' ').map(Number);  // ゴール
   const Point = [
      [sy, sx]
   ];
   const grid = [];
   for (let h = 0; h < H; h++) {
      grid.push(lines.shift().split(''));
   }
   grid[sy][sx] = '*';
   const T = BFS(Point, [], 0);
   console.log(grid[gy][gx] === '*' ? T : 'No');
});
hogeちゃんの画像

upしました。

コメント