题目链接:https://vjudge.net/problem/POJ-3984
这个题目,emm,上代码,看的估计应该是刚开始接触搜索的,我带点注释,你能慢慢理解。
#include <iostream>
#include <cstring>
#include<vector>
#include<string>
#include <cmath>
#include <map>
#include <queue>
#include <algorithm>
using namespace std; #define inf (1LL << 31) - 1
#define rep(i,j,k) for(int i = (j); i <= (k); i++)
#define rep__(i,j,k) for(int i = (j); i < (k); i++)
#define per(i,j,k) for(int i = (j); i >= (k); i--)
#define per__(i,j,k) for(int i = (j); i > (k); i--) const int N = ;
int mv_x[] = { , , -, }; //(1)
int mv_y[] = { , -, , }; //(2) (1) + (2) 可以表示人的上下左右移动
char mp[N][N]; //地图
bool vis[N][N]; //有没有访问过了 struct node{
int x, y;
vector<string> vec;
node(){}
node(int a, int b){
x = a;
y = b;
}
}; inline void input(){ rep__(i, , ) rep__(j, , ) cin >> mp[i][j];
} //检查有无越界的函数
inline bool check(int x, int y){
return x >= && x <= && y >= && y <= ;
} void fun(string& p){
cout << p << endl;
} void work(){ //开始的处理,起点标记
vis[][] = true;
node T(, );
T.vec.push_back("(0, 0)"); queue<node> que;
que.push(T); while (!que.empty()){ node tmp = que.front();
que.pop(); rep__(p, , ){ //人的移动
int dx = tmp.x + mv_x[p];
int dy = tmp.y + mv_y[p]; //没越界 是可以走的 没访问过
if (check(dx, dy) && mp[dx][dy] == '' && !vis[dx][dy]){
vis[dx][dy] = true; //标记 node in = tmp;
in.x = dx;
in.y = dy;
string t = "(x, x)";
t[] = '' + dx;
t[] = '' + dy;
in.vec.push_back(t); //把新的点压入 if (dx == && dy == ){ //遇到了出口,输出路线 for_each(in.vec.begin(), in.vec.end(), fun); return;
}
que.push(in); //把新的状态压入队列
}
}
}
} int main(){ ios::sync_with_stdio(false);
cin.tie(); input();
work(); return ;
}