#include<iostream> #include <queue> #include<string.h> using namespace std; int m,n,flag; typedef struct point { int x,y; point *previous; int step; } point; point dir[8] = { { -1, 1, NULL, 0 }, { 0, 1, NULL, 0 }, { 1, 1, NULL, 0 }, { 1, 0, NULL, 0 }, { 1, -1, NULL, 0 }, { 0, -1, NULL, 0 }, { -1, -1, NULL, 0 }, { -1, 0, NULL, 0 }, }; int map[20][20]; void Print(point *p) { int shortest = p->step; while (p->previous!= NULL) { cout << "(" << p->x << "," << p->y << ")"<<' '; p=p->previous; } cout << "(" << p->x<< "," << p->y << ")" << ' '<<endl; } void BFS(point startPoint) { queue<point> q; q.push(startPoint); point cur; while (!q.empty()) { cur = q.front(); q.pop(); map[cur.x][cur.y] = 1; for (int i = 0; i < 8; i++) { point nxt{ cur.x + dir[i].x, cur.y + dir[i].y, NULL, 0 }; if (nxt.x > 0 && nxt.x <= m && nxt.y > 0 && nxt.y <= n && map[nxt.x][nxt.y] == 0) { point *tmp = new point; memcpy(tmp, &cur, sizeof(point)); nxt.previous = tmp; nxt.step = cur.step + 1; map[nxt.x][nxt.y] = 1; if (nxt.x==m&&nxt.y==n) { Print(&nxt); flag=1; return; } q.push(nxt); } } } } int main() { int i,j; memset(map, 1, sizeof(map)); flag=0; cin>>m>>n; for (i = 1; i <= m; i++) for (j = 1; j <= n; j++) cin>>map[i][j]; point startPoint={ 1, 1, NULL, 0 }; BFS(startPoint); }