带记录前驱的bfs
#include <iostream> #include <queue> #include <cstring> #include <string> using namespace std; class node{ public: int x,y,t; string direction; node(int argx=0,int argy=0,int argt=0,string args=""):x(argx),y(argy),t(argt),direction(args) {} void makenode(string s) { x=s[1]-'0'; y=s[0]-'a'+1; t=0; direction=""; } bool operator==(const node& a) const { return a.x==x&&a.y==y; } }; string s,t; node b,e; int c[10][10]; node p[10][10]; int go[8][2]={{-1,0},{1,0},{0,1},{0,-1},{-1,-1},{-1,1},{1,-1},{1,1}}; string dir[8]={"D","U","R","L","LD","RD","LU","RU"}; void bfs() { queue<node> q; q.push(b); c[b.x][b.y]=-1; while(!q.empty()) { node temp=q.front(); q.pop(); if(temp==e) { e.direction=temp.direction; cout << temp.t << endl; break; } for(int i=0;i<8;i++) { int nextx=temp.x+go[i][0]; int nexty=temp.y+go[i][1]; if(nextx>=1&&nextx<=8&&nexty>=1&&nexty<=8&&c[nextx][nexty]==0) { c[nextx][nexty]=-1; q.push(node(nextx,nexty,temp.t+1,dir[i])); p[nextx][nexty]=temp; } } c[temp.x][temp.y]=1; } } void print_path(node begin,node end) { if(end==begin) return; else { print_path(begin,p[end.x][end.y]); cout << end.direction << endl; } } int main() { cin >> s >> t; b.makenode(s); e.makenode(t); bfs(); print_path(b,e); return 0; }