最短経路の探索

なんか迷路の最短経路を求めよっていう問題がはやってるっぽいので解いてみた。いつもはC++を使ってるけど、今日はなんとなくCで書いてみた。アルゴリズムは幅優先探索。

#include <stdio.h>
#include <string.h>

#define N (100+2)

char field[N][N];
int yqueue[N*N], xqueue[N*N];
int yprev[N][N], xprev[N][N];
const int dy[] = {-1, 0, 1, 0};
const int dx[] = {0, -1, 0, 1};

int main(void)
{
  int i = 0, h = 0, first = 0, last = 0;
  while (fgets(field[h], N, stdin)) {
    char *p = strchr(field[h], 'S');
    if (p != NULL) {
      yqueue[last] = h;
      xqueue[last] = p - field[h];
      last++;
    }
    h++;
  }
  memset(yprev, -1, sizeof(yprev));
  memset(xprev, -1, sizeof(xprev));
  while (first < last) {
    int y = yqueue[first], x = xqueue[first];
    first++;
    if (field[y][x] == 'G') {
      int yp = yprev[y][x], xp = xprev[y][x];
      for (y = yp, x = xp; field[y][x] != 'S'; y = yp, x = xp) {
        field[y][x] = '$';
        yp = yprev[y][x], xp = xprev[y][x];
      }
      for (i = 0; i < h; i++)
        printf("%s", field[i]);
      break;
    }
    for (i = 0; i < 4; i++) {
      int yn = y + dy[i], xn = x + dx[i];
      if (field[yn][xn] != '*' && yprev[yn][xn] == -1) {
        yprev[yn][xn] = y, xprev[yn][xn] = x;
        yqueue[last] = yn, xqueue[last] = xn;
        last++;
      }
    }
  }
  return 0;
}

周囲が壁で囲われてることと、迷路の幅と高さが100を超えないことを仮定してる。

C++だとstd::queueとかstd::pairとかがあるけど、Cにはそんな便利なものはないので配列で代用してる。C++の標準ライブラリのありがたみを感じる。