题目描述
Dpstr最近迷上了推冰块。冰地是一个n行m列的网格区域，第i行第j列的格子记为(i,j)，也就是左上角为(1,1)，右下角为(n,m)。每个格子可能是冰面、障碍物、减速带三者之一。其中，冰地外围（即第0行、第n+1行、第0列、第m+1列）的所有格子均有障碍物。除此之外，冰地内共有k个障碍物和减速带，其余格子为冰面。
初始时，有一个冰块位于(1,1)处。Dpstr每次可以选择上、下、左、右四个方向之一推动该冰块，推动后该冰块将一直沿此方向移动，直到冰块所在的格子为减速带，或冰块沿运动方向的下一个格子为障碍物时，冰块将停止运动。一旦冰块停在减速带上，该减速带即消失。
Dpstr希望通过尽量少的推动次数使得冰块停在(n,m)处。请计算Dpstr至少要推多少次冰块。
数据范围
对于30%的数据，2≤n≤5，2≤m≤5，0≤k≤5；
对于50%的数据，2≤n≤1,000，2≤m≤1,000，0≤k≤1,000；
对于70%的数据，2≤n≤50,000，2≤m≤50,000，0≤k≤50,000；
对于100%的数据，2≤n≤1,000,000,000，2≤m≤1,000,000,000，0≤k≤50,000，1≤xi≤n，1≤yi≤m，0≤ti≤1。
解法
显然每个格子最多只会走一次。
所以可以使用BFS。
运用二分解决滑行问题。
代码
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#define ll long long
using namespace std;
const char* fin="ice.in";
const char* fout="ice.out";
const ll inf=0x7fffffff;
const ll maxn=50007,maxt=1000007;
const ll fx[4][2]={{0,-1},{-1,0},{1,0},{0,1}};
ll n,m,n1,i,j,k,l,ans=inf;
struct node{
ll x,y,z;
void operator =(const node &j){
x=j.x;
y=j.y;
z=j.z;
}
}f[maxn],g[maxn];
ll b[maxt][2],head,tail;
ll h[maxt],dis[maxt];
ll hash(ll x){
ll t=x%maxt;
while (h[t] && h[t]!=x) t=(t+1)%maxt;
return t;
}
ll pos(ll x,ll y){
return (x-1)*m+y;
}
void add(ll x,ll y,ll z){
ll k=pos(x,y),i,j;
i=hash(k);
if (!h[i]) {
h[i]=k;
dis[i]=z;
b[++tail][0]=x;
b[tail][1]=y;
}
}
void bfs(ll x,ll y){
ll xx[4],yy[4],i,j,k,dist,now,l,r,mid,o;
bool bz[4];
add(x,y,0);
while (head++<tail){
j=b[head][0];
k=b[head][1];
now=hash(pos(j,k));
memset(bz,0,sizeof(bz));
l=1;
r=n1;
while (l<r){
mid=(l+r+1)/2;
if (f[mid].x<j || f[mid].x==j && f[mid].y<k) l=mid;
else r=mid-1;
}
for (o=l;o<=l+2;o++){
if (o>n1) break;
if (f[o].x==j && f[o].y<k) {
xx[0]=f[o].x;
yy[0]=f[o].y+(f[o].z==0);
bz[0]=true;
}
if (f[o].x==j && f[o].y>k){
xx[1]=f[o].x;
yy[1]=f[o].y-(f[o].z==0);
bz[1]=true;
break;
}
}
if (!bz[0]) xx[0]=j,yy[0]=1;
if (!bz[1]) xx[1]=j,yy[1]=m;
l=1;
r=n1;
while (l<r){
mid=(l+r+1)/2;
if (g[mid].y<k || g[mid].y==k && g[mid].x<j) l=mid;
else r=mid-1;
}
for (o=l;o<=l+2;o++){
if (o>n1) break;
if (g[o].y==k && g[o].x<j) {
xx[2]=g[o].x+(g[o].z==0);
yy[2]=g[o].y;
bz[2]=true;
}
if (g[o].y==k && g[o].x>j){
xx[3]=g[o].x-(g[o].z==0);
yy[3]=g[o].y;
bz[3]=true;
break;
}
}
if (!bz[2]) xx[2]=1,yy[2]=k;
if (!bz[3]) xx[3]=n,yy[3]=k;
for (i=0;i<4;i++){
add(xx[i],yy[i],dis[now]+1);
if (xx[i]==n && m==yy[i]) ans=min(ans,dis[now]+1);
}
}
}
bool cmp(node a,node b){
return a.x<b.x || a.x==b.x && a.y<b.y;
}
bool cmp1(node a,node b){
return a.y<b.y || a.y==b.y && a.x<b.x;
}
int main(){
freopen(fin,"r",stdin);
freopen(fout,"w",stdout);
scanf("%d%d%d",&n,&m,&n1);
for (i=1;i<=n1;i++) scanf("%d%d%d",&f[i].x,&f[i].y,&f[i].z),g[i]=f[i];
sort(f+1,f+n1+1,cmp);
sort(g+1,g+n1+1,cmp1);
bfs(1,1);
printf("%lld",ans);
return 0;
}启发
对于搜索题，从最简单的搜索入手。
初始搜索最好打bfs，因为最容易优化，而且最短路最快找到。
然后根据客观的时间耗费，优化对应的地方。