【BZOJ 1193】 [HNOI2006]马步距离

在这里输入题意

【题解】

原问题可以等价为两个点。
然后其中一个点要移动到另外一个点。
那么我们可以把左下角那个点(对称总是可以得到一个点在左下角)放在原点的位置。
然后通过x坐标差和y坐标差。
获取出来,另外一个点的相对位置。
然后问题就转化成
从原点(0,0)出发,到达点(|xp-xs|,|yp-ys|)的问题了
设那个点为(x,y)

这个问题在大范围内。

即当x>10或者y>10的时候。可以谈心地解。

即直接让他往(0,0)的方向贪心跳

直到x<10且y<10就好

(每次跳的时候,如果x>y那么x-=2,y-=1,如果x<=y那么y-=2,x-=1

(如果x或者y变成负数了,那么直接取绝对值就好。因为下一步总是能跳回来的

(变成负数,肯定是0->-1了,那么我们就把它改成往里面跳就好了,那么就是变成1了而不是-1,所以直接取绝对值是没问题的。

【代码】

#include <bits/stdc++.h>

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define all(x) x.begin(),x.end()

#define pb push_back

#define lson l,mid,rt<<1

#define rson mid+1,r,rt<<1|1

using namespace std;

const double pi = acos(-1);

const int dx[8] = {-1,-2,-2,-1,1,2,2,1};

const int dy[8] = {-2,-1,1,2,2,1,-1,-2};

const int N = 20;

const int INF = 0x3f3f3f3f;

int xp,yp,xs,ys,ans;

int dis[N+10][N+10];

queue<pair<int,int> > dl;

int main(){

	#ifdef LOCAL_DEFINE

	    freopen("rush_in.txt", "r", stdin);

	#endif

	scanf("%d%d%d%d",&xp,&yp,&xs,&ys);

	xp = abs(xp-xs);

	yp = abs(yp-ys);

	while (xp > 10 || yp>10){

        if (xp>yp){

            xp-=2;

            yp-=1;

        }else {

            yp-=2;

            xp-=1;

        }

        xp = abs(xp);yp = abs(yp);

        ans++;

	}

    dl.push(make_pair(0,0));

    memset(dis,INF,sizeof dis);

    dis[0][0] = 0;

    while (!dl.empty()){

        int x = dl.front().first,y = dl.front().second;

        dl.pop();

        for (int i = 0;i < 8;i++){

            int tx = x+dx[i],ty = y + dy[i];

            if (tx<-1 || ty<-1 || tx>11 || ty>11) continue;

            if (dis[tx][ty]>dis[x][y]+1){

                dis[tx][ty] = dis[x][y] + 1;

                dl.push(make_pair(tx,ty));

            }

        }

    }

    printf("%d\n",ans+dis[xp][yp]);

	return 0;

}

巴特西

【BZOJ 1193】 [HNOI2006]马步距离

最新文章

热门文章