【JZOJ4861】【NOIP2016提高A組集訓第7場11.4】推冰塊

題目描述

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，因為最容易優化，而且最短路最快找到。
然后根據客觀的時間耗費，優化對應的地方。