bfs

gistfile1.d

import std.stdio;
import std.conv;
import std.range;
import std.array;
import std.string;
import std.algorithm;
import std.typecons;

alias Tuple!(int, "x", int, "y") P;
 
void main(string[] args)
{

  auto map_str = `#S######.#
......#..#
.#.##.##.#
.#........
##.##.####
....#....#
.#######.#
....#.....
.####.###.
....#...G#
`;
  auto map = split(map_str);

  auto width = map[0].length;
  auto height = map.length;

  // 距離配列の初期化
  auto dists = new int[][](height, width);
  foreach (line; dists) {
    foreach (ref dist; line) {
      dist = -1;
    }
  }

  // 開始地点を求める
  int sx, sy;
  foreach (y, str; map) {
    auto x = std.string.indexOf(str, 'S');
    if (x != -1) {
      sx = to!(int)(x);
      sy = to!(int)(y);
      break;
    }
  }
  dists[sy][sx] = 0;

  auto diffs = [
    P(0, 1),
    P(1, 0),
    P(-1, 0),
    P(0, -1),
    ];

  P[] queue;

  queue.insertInPlace(0, P(sx, sy));

  while (!queue.empty) {
    auto current = queue.back;
    queue.popBack();

    // 距離の確定
    auto x = current.x;
    auto y = current.y;

    if ('G' == map[y][x]) {
      // ゴールなので距離を出力
      writeln("dist:", dists[y][x]);
      break;
    }

    foreach (diff; diffs) {
      auto nx = x + diff.x;
      auto ny = y + diff.y;

      // 境界値チェック
      if (nx < 0 || width <= nx) continue;
      if (ny < 0 || height <= ny) continue;

      // 壁は無視
      if ('#' == map[ny][nx]) continue;

      // 他ルートで到達済み
      if (-1 != dists[ny][nx]) continue;

      // 距離を記録
      dists[ny][nx] = dists[y][x] + 1;

      queue.insertInPlace(0, P(nx, ny));
    }
 }
}