好奇怪的游戏
题目 好奇怪的游戏
思路分析
本来想着可能只需要往左上角的方向走 不需要12个方向都走 这样做个优化
但是居然ac了……就懒得写那么多了
代码实现
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef pair<int,int> PII;
const int N=25;
int d[N][N];
int dx[12]={-2,-2,-1,1,2,2,2,2,1,-1,-2,-2};
int dy[12]={1,2,2,2,2,1,-1,-2,-2,-2,-2,-1};
bool isVaild(int x,int y){
return x>=1 && x<=N && y>=1 && y<=N && d[x][y]==-1;
}
int bfs(int x,int y){
queue<PII> q;
memset(d,-1,sizeof d);
q.push({x,y});
d[x][y]=0;
while(!q.empty()){
auto cur=q.front();q.pop();
int ux=cur.first,uy=cur.second;
for(int i=0;i<12;i++){
int nx=ux+dx[i],ny=uy+dy[i];
if(isVaild(nx,ny)){
d[nx][ny]=d[ux][uy]+1;
q.push({nx,ny});
}
}
}
return d[1][1];
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int x1,y1,x2,y2;
cin>>x1>>y1;
cout<<bfs(x1,y1)<<endl;
cin>>x2>>y2;
cout<<bfs(x2,y2)<<endl;
return 0;
}
💬 评论