#include #include #include #include #include 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 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 path; while (cur != NULL) { sprintf(pos, "(%d, %d)", cur->row, cur->col); path.push_back(pos); cur = cur->pre; } for (vector::reverse_iterator cur = path.rbegin(); cur != path.rend(); ++cur) printf("%s\n", cur->c_str()); return 0; }