leetcode-go/poj/3984.maze/main.cc

#include <algorithm>
#include <cstdio>
#include <queue>
#include <string>
#include <vector>

using namespace std;

const int N = 5;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

char pos[7];

struct Grid {
  bool way;
  int row;
  int col;
  Grid *pre;
};

Grid maze[N][N];

int main() {
  for (int i = 0, k; i < N; i++) {
    for (int j = 0; j < N; j++) {
      scanf("%d", &k);
      maze[i][j].way = k == 0;
      maze[i][j].row = i;
      maze[i][j].col = j;
      maze[i][j].pre = NULL;
    }
  }
  queue<Grid> q;
  q.push(maze[0][0]);
  while (q.size() != 0) {
    Grid &g = q.front();
    q.pop();
    if (g.col == N - 1 && g.row == N - 1) break;
    for (int i = 0, nx, ny; i < 4; i++) {
      nx = g.row + dx[i];
      ny = g.col + dy[i];
      if (nx < 0 || N <= nx || ny < 0 || N <= ny) continue;
      Grid &ng = maze[nx][ny];
      if (!ng.way || ng.pre != NULL) continue;
      ng.pre = &g;
      q.push(ng);
    }
  }
  Grid *cur = &maze[N - 1][N - 1];
  vector<string> path;
  while (cur != NULL) {
    sprintf(pos, "(%d, %d)", cur->row, cur->col);
    path.push_back(pos);
    cur = cur->pre;
  }
  for (vector<string>::reverse_iterator cur = path.rbegin(); cur != path.rend(); ++cur)
    printf("%s\n", cur->c_str());
  return 0;
}