【机器人移动】暴力dfs和层次遍历bfs

暴力，深搜每一种可能，使用

struct vertice{
int x,y;
bool operator<(onst vertice& other)const{if(x != other.x)return x < other.x;return y < other.y;}
}
vertice v={x,y};

保存顶点，使用map:

map<vertice,int> mp;
vertice v = {x,y};
mp.insert({v,1});

来插入键值；
使用mp.count(v)来判断是否已经有该点被访问过；

然后dfs深搜遍历；

正确做法：bfs广搜；
并且，使用dx,dy来存入移动的方向，减少代码量；

其中，关键是我们使用step存放限制步数，用于停止运行；
因此bfs队列的结构是queue<pair<vertice,int>> q;分别是点和step;
代码如下：

#include<iostream>
#include<map>
#include<queue>
using namespace std;
int n,k;
int x0,y0;
struct vertice{int x,y;bool operator<(const vertice& other) const {if (x != other.x) return x < other.x;return y < other.y;}
};//点集
map<vertice,int> mp;bool isValid(int x,int y){return (1<=x&&x<=n)&&(1<=y&&y<=n);
}
int dx[8] = {-1,-2,-2,-1,1,2,2,1};
int dy[8] = {2,1,-1,-2,-2,-1,1,2};int main(){cin >> n >> k;cin >>x0 >>y0;queue<pair<vertice,int>> q;vertice v = {x0,y0};mp.insert({v,1});q.push({v,0});while(!q.empty()){auto [cur,step] = q.front();//也可以写成：pair<vertice,int> temp = q.front();//vertice cur = temp.first;//int step = temp.second;//写成auto [cur,step] = q.front()；属于简化的写了；q.pop();if(step == k)continue;step++;for(int i = 0;i < 8;i++){if(isValid(cur.x+dx[i],cur.y+dy[i])){vertice v = {cur.x+dx[i],cur.y+dy[i]};if(mp.count(v)==0){mp.insert({v,1});q.push({v,step});}}}}cout << mp.size()<<endl;
}