#include<stdio.h> int map[5][5]={0,1,0,0,0, 0,1,0,1,0, 0,0,0,0,0, 0,1,1,1,0, 0,0,0,1,0}; int mx[4]={1,-1,0,0}; int my[4]={0,0,1,-1}; int q; typedef struct node { int x; int y; int step; int pre; }node; node dui[100]; int tou=0; int wei=1; void bfs() { int nx; int ny; dui[tou].x=0; dui[tou].y=0; dui[tou].step=1; dui[tou].pre =-1; map[0][0]=0; while(tou<wei) { if(dui[tou].x ==4&&dui[tou].y==4) { q=tou; printf("%d\n",dui[tou].step); break; } for(int i=0;i<4;i++) { nx=dui[tou].x +mx[i]; ny=dui[tou].y +my[i]; if(nx>=0&&nx<5&&ny>=0&&ny<5&&map[nx][ny]==0) { dui[wei].x =nx; dui[wei].y =ny; dui[wei].step =dui[tou].step +1; map[nx][ny]=dui[tou].step +1; dui[wei].pre =tou; wei++; } } tou++; }
} void prin(int i) { if(i==-1) return; prin(dui[i].pre ); printf("(%d,%d)\n",dui[i].x ,dui[i].y ); } int main() { bfs(); prin(q); return 0; }