最少步数 南工acm58

先把距离为1可以到的位置存起来，然后由距离为一的位置找距离为2的位置，再由距离为2的位置找距离为3的位置存起来。。。

每次找完位置后，判断要到的地方在不在这次找到的距离为d的位置里，如果在，就结束，输出d，不在，就继续找！

# include <iostream># include <vector># include <string.h>using namespace std;bool map[9][9]={{1,1,1,1,1,1,1,1,1},{1,0,0,1,0,0,1,0,1},{1,0,0,1,1,0,0,0,1},{1,0,1,0,1,1,0,1,1},{1,0,0,0,0,1,0,0,1},{1,1,0,1,0,1,0,0,1},{1,1,0,1,0,1,0,0,1},{1,1,0,1,0,0,0,0,1},{1,1,1,1,1,1,1,1,1}};bool m[9][9];//标志数组struct data{int x, y;};vector<data> s[64];//存放距离分别为1，2，3...的位置int main(){int n, flag, i, j, k;data a, b, t;cin>>n;while (n--){memset(m, 0, sizeof(m));memset(s, 0, sizeof(s));cin>>a.x>>a.y>>b.x>>b.y;s[0].push_back(a);flag = 0;if (a.x==b.x&&a.y==b.y){cout<<"0\n";continue;}for (i = 0; i<64; i++){for (j = 0; j<s[i].size(); j++){if (!m[s[i][j].x+1][s[i][j].y] && !map[s[i][j].x+1][s[i][j].y])//判断是否已经找过该点，和该点是不是空地，不是空地就继续找下一个距离的点{t.x = s[i][j].x+1; t.y = s[i][j].y; s[i+1].push_back(t);m[s[i][j].x+1][s[i][j].y]=1;}if (!m[s[i][j].x-1][s[i][j].y] && !map[s[i][j].x-1][s[i][j].y]){t.x = s[i][j].x-1; t.y = s[i][j].y; s[i+1].push_back(t);m[s[i][j].x-1][s[i][j].y]=1;}if (!m[s[i][j].x][s[i][j].y+1] && !map[s[i][j].x][s[i][j].y+1]){t.x = s[i][j].x; t.y = s[i][j].y+1; s[i+1].push_back(t);m[s[i][j].x][s[i][j].y+1]=1;}if (!m[s[i][j].x][s[i][j].y-1] && !map[s[i][j].x][s[i][j].y-1]){t.x = s[i][j].x; t.y = s[i][j].y-1; s[i+1].push_back(t);m[s[i][j].x][s[i][j].y-1]=1;}}for (k = 0; k<s[i+1].size(); k++)//判断要到的位置是不是已经找到{if (s[i+1][k].x == b.x&&s[i+1][k].y==b.y)flag = 1;}if (flag)//找到该点，flag=1，跳出循环，并输出步数break;}cout<<i+1<<endl;}return 0;}