題目描述

Dpstr最近迷上了推冰塊。冰地是一個(gè)n行m列的網(wǎng)格區(qū)域，第i行第j列的格子記為(i,j)，也就是左上角為(1,1)，右下角為(n,m)。每個(gè)格子可能是冰面、障礙物、減速帶三者之一。其中，冰地外圍（即第0行、第n+1行、第0列、第m+1列）的所有格子均有障礙物。除此之外，冰地內(nèi)共有k個(gè)障礙物和減速帶，其余格子為冰面。
初始時(shí)，有一個(gè)冰塊位于(1,1)處。Dpstr每次可以選擇上、下、左、右四個(gè)方向之一推動(dòng)該冰塊，推動(dòng)后該冰塊將一直沿此方向移動(dòng)，直到冰塊所在的格子為減速帶，或冰塊沿運(yùn)動(dòng)方向的下一個(gè)格子為障礙物時(shí)，冰塊將停止運(yùn)動(dòng)。一旦冰塊停在減速帶上，該減速帶即消失。
Dpstr希望通過(guò)盡量少的推動(dòng)次數(shù)使得冰塊停在(n,m)處。請(qǐng)計(jì)算Dpstr至少要推多少次冰塊。

數(shù)據(jù)范圍

對(duì)于30%的數(shù)據(jù)，2≤n≤5，2≤m≤5，0≤k≤5；
對(duì)于50%的數(shù)據(jù)，2≤n≤1,000，2≤m≤1,000，0≤k≤1,000；
對(duì)于70%的數(shù)據(jù)，2≤n≤50,000，2≤m≤50,000，0≤k≤50,000；
對(duì)于100%的數(shù)據(jù)，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。

解法

顯然每個(gè)格子最多只會(huì)走一次。
所以可以使用BFS。
運(yùn)用二分解決滑行問(wèn)題。

代碼

#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; }

啟發(fā)

對(duì)于搜索題，從最簡(jiǎn)單的搜索入手。
初始搜索最好打bfs，因?yàn)樽钊菀變?yōu)化，而且最短路最快找到。
然后根據(jù)客觀的時(shí)間耗費(fèi)，優(yōu)化對(duì)應(yīng)的地方。

轉(zhuǎn)載于:https://www.cnblogs.com/hiweibolu/p/6714847.html

總結(jié)

以上是生活随笔為你收集整理的【JZOJ4861】【NOIP2016提高A组集训第7场11.4】推冰块的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。