本文主要是介绍【bzoj1193】[HNOI2006]马步距离，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
嗯嗯嗯~~~~~
普及一个小知识。。。
马从(x1,y1)到(x2,y2)相当于马从(abs(x1-x2),abs(y1-y2))到(0,0)。
这样子就可以不怕大数了~~~
这道题要大范围贪心+小范围BFS
规定(abs(x1-x2)+abs(y1-y2))大于某一个数就是大范围。
在大范围内，直接贪心。
while(x+y>50){x=max(x,y);if(x-4>2*y)x-=4;else x-=4,y-=2;ans+=2;}如果x-4>2*y 直走。 否则斜上方走。 此处x=abs(x1-x2),y=abs(y1-y2)
代码：
#include <algorithm>
#include <algorithm>
#include <iostream>
#include<string.h>
#include <fstream>
#include <math.h>
#include <vector>
#include <cstdio>
#include <string>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define exp 1e-8
#define fi first
#define se second
#define ll long long
#define INF 0x3f3f3f3f
#define lson l,mid,rt<<1
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define rson mid+1,r,(rt<<1)+1
#define all(a) a.begin(),a.end()
#define mm(a,b) memset(a,b,sizeof(a));
#define for1(a,b) for(int a=1;a<=b;a++)//1---(b)
#define rep(a,b,c) for(int a=b;a<=c;a++)//b---c
#define repp(a,b,c)for(int a=b;a>=c;a--)///
using namespace std;
void bug(string m="here"){cout<<m<<endl;}
template<typename __ll> inline void READ(__ll &m){__ll x=0,f=1;char ch=getchar();while(!(ch>='0'&&ch<='9')){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}m=x*f;}
template<typename __ll>inline void read(__ll &m){READ(m);}
template<typename __ll>inline void read(__ll &m,__ll &a){READ(m);READ(a);}
template<typename __ll>inline void read(__ll &m,__ll &a,__ll &b){READ(m);READ(a);READ(b);}
template<typename __ll>inline void read(__ll &m,__ll &a,__ll &b,__ll &c){READ(m);READ(a);READ(b);READ(c);}
template < class T > T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template < class T > T lcm(T a, T b) { return a / gcd(a, b) * b; }
template < class T > inline void rmin(T &a, const T &b) { if(a > b) a = b; }
template < class T > inline void rmax(T &a, const T &b) { if(a < b) a = b; }
template < class T > T pow(T a, T b) { T r = 1; while(b > 0) { if(b & 1) r = r * a; a = a * a; b /= 2; } return r; }
template < class T > T pow(T a, T b, T mod) { T r = 1; while(b > 0) { if(b & 1) r = r * a % mod; a = a * a % mod; b /= 2; } return r; }int dx[8]={1,1,-1,-1,2,2,-2,-2};
int dy[8]={2,-2,2,-2,1,-1,1,-1};
int dist[110][110];
int x,y,ans=0;
void bfs()
{mm(dist,-1);queue<int>quex;queue<int>quey;dist[x][y]=0;quex.push(x),quey.push(y);while(!quex.empty()){int x=quex.front();quex.pop();int y=quey.front();quey.pop();for(int i=0;i<8;i++){int newx=x+dx[i];int newy=y+dy[i];if(newx<0||newx>110||newy<0||newy>110)continue;if(dist[newx][newy]!=-1)continue;dist[newx][newy]=dist[x][y]+1;if(newx==50&&newy==50)return ;quex.push(newx),quey.push(newy);}}
}
int main()
{int x1,y1,x2,y2;read(x1,y1),read(x2,y2);x=abs(x1-x2),y=abs(y1-y2);while(x+y>50){if(x<y)swap(x,y);if(x-4>2*y)x-=4;else x-=4,y-=2;ans+=2;}//大范围结束 直接求（0,0）到（x,y）的最小距离。x+=50,y+=50; //但是x可为负，加上一个数确保为整数bfs();//即求（50,50）到（x+50,y+50）的最小距离。printf("%d\n",ans+dist[50][50]);return 0;
}这篇关于【bzoj1193】[HNOI2006]马步距离的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
