小X与机器人(搜索，几何)

题目描述：

法1：爆搜

#include<iostream>
#include<queue>
#include<cstring>
#include<algorithm>
#define pii pair<int,int>
using namespace std;
const int N=20;
int a,b,c,d;
int f[N][N],dis[N][N];
int x[4]={-1,0,1,0},y[4]={0,1,0,-1};
int bfs(){
    queue<pii> q;
    q.push({a,b});
    dis[a][b]=0;
    while(q.size()){
        auto t=q.front(); q.pop();
        for(int i=0;i<4;i++){
            int X=t.first+x[i],Y=t.second+y[i];
            if (!f[X][Y]) continue;
            if(dis[X][Y]>dis[t.first][t.second]+1){
                dis[X][Y]=dis[t.first][t.second]+1;
                q.push({X,Y});
            }
            if(X==c&&Y==d)return dis[X][Y];
        }
    }
}
int main(){
	for(int i=1;i<=19;i++)
		f[i][1]=f[i][19]=f[1][i]=f[19][i]=1;
	memset(dis,0x3f,sizeof dis);
	cin>>a>>b>>c>>d;
    cout<<bfs();
    return 0;
}

法2：枚举几何情况

#include<iostream>
using namespace std;
const int N=3e5+10;
int n,m,a[N],maxn[N];
int main(){
    int x1,y1,x2,y2;
	cin>>x1>>y1>>x2>>y2;
    if(x1==x2)cout<<abs(y1-y2);//同边 
    else if(y1==y2)cout<<abs(x1-x2);//同边
    else{
        if(x1==1&&x2==19||(x2==1&&x1==19))//对边 
            cout<<18+min(38-(y1+y2),y1+y2-2);        
        else if((y1==1&&y2==19)||(y2==1&&y1==19))//对边
            cout<<18+min(38-(x1+x2),x1+x2-2);       
        else//临边
        	cout<<abs(x1-x2)+abs(y1-y2)<<endl;      
    }  
    return 0;
}

法3：另一种枚举几何情况的思路

#include <iostream>
using namespace std;
int a,b,c,d;
int dis(int a,int b,int c,int d){return (a-c)*(a-c)+(b-d)*(b-d);}
void f(int &x,int &y){
	int k,dit=1e9;
	if((k=dis(a,b,1,1)+dis(c,d,1,1))<dit)dit=k,x=1,y=1;	
	if((k=dis(a,b,1,19)+dis(c,d,1,19))<dit)dit=k,x=1,y=19;	
	if((k=dis(a,b,19,1)+dis(c,d,19,1))<dit)dit=k,x=19,y=1;	
	if((k=dis(a,b,19,19)+dis(c,d,19,19))<dit)dit=k,x=19,y=19;	
}
int main(){
	cin>>a>>b>>c>>d;
	int x,y;
	f(x,y);
	if(a==c||b==d){cout<<abs(a-c)+abs(b-d);}
	else cout<<abs(a-x)+abs(b-y)+abs(c-x)+abs(d-y);
	return 0;
}

最后

以上就是还单身大白为你收集整理的小X与机器人(搜索，几何)的全部内容，希望文章能够帮你解决小X与机器人(搜索，几何)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。