BZOJ 1193 [HNOI2006]马步距离:大范围贪心 小范围暴搜

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1193

题意:

  给定起点(px,py)、终点(sx,sy)。(x,y < 10000000)

  每一步只能走“日”字(象棋中的马走日),坐标可以为负。

  问你从起点到终点最少走多少步。

题解:

  简化问题:

    (1)从(px,py)到(sx,sy)等价于:从(abs(px-sx), abs(py-sy))到(0,0)。

    (2)从(x,y)到(0,0)等价于:从(y,x)到(0,0)。

    所以原题简化成:从(abs(px-sx), abs(py-sy))到(0,0),并且可以随时交换x,y以保证x > y。

  大范围贪心:

    为了方便起见,始终保证x > y。

    那么对于任意一个数据的最短路径都可以等价为如下形式:

    BZOJ 1193 [HNOI2006]马步距离:大范围贪心 小范围暴搜

    左边部分直走(先右下,再右上),右边部分往右上方走,直到接近终点时停止贪心(x+y <= 50)。

    同时为了保证没有过多的直走(直走会浪费2个距离),设定直走的前提为:

      右边区域的长宽x,y满足:((x-4)/y) > 2

      也就是:x-4 > y*2

    每直走一次,ans+=2。往右上走一次,ans++。

  小范围暴搜:

    bfs.

    很好写,不说了。。。

    注意:为了不偏离终点太远,限定可继续搜索的点要满足:abs(nx)<=100 && abs(ny)<=100

AC Code:

 #include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <queue>
#define MAX_R 105 using namespace std; const int dx[]={,,,,-,-,-,-};
const int dy[]={,,-,-,,,-,-}; struct Coor
{
int x;
int y;
Coor(int _x,int _y)
{
x=_x;
y=_y;
}
Coor(){}
}; int x,y;
int px,py;
int sx,sy;
int ans=;
int dis[MAX_R][MAX_R];
bool vis[MAX_R][MAX_R];
queue<Coor> q; void read()
{
cin>>px>>py>>sx>>sy;
x=abs(px-sx);
y=abs(py-sy);
} Coor get_front()
{
Coor now=q.front();
q.pop();
return now;
} void insert(Coor now)
{
if(vis[now.x][now.y]) return;
q.push(now);
vis[now.x][now.y]=true;
} void bfs()
{
memset(dis,-,sizeof(dis));
dis[x][y]=;
insert(Coor(x,y));
while(!q.empty())
{
Coor now=get_front();
int nx=now.x;
int ny=now.y;
if(nx== && ny==) return;
if(abs(nx)> || abs(ny)>) continue;
for(int i=;i<;i++)
{
int tx=nx+dx[i];
int ty=ny+dy[i];
if(dis[tx][ty]==-)
{
dis[tx][ty]=dis[nx][ny]+;
insert(Coor(tx,ty));
}
}
}
} void solve()
{
while(x+y>)
{
if(x<y) swap(x,y);
if(x->y*)
{
x-=;
ans+=;
}
else
{
x-=;
y--;
ans++;
}
}
bfs();
ans+=dis[][];
} void print()
{
cout<<ans<<endl;
} int main()
{
read();
solve();
print();
}
上一篇:webpack 教程 那些事儿03-webpack两大精华插件,热加载


下一篇:【Linux基础】大B和小b