POJ3009 Curling2.0 题解

CSDN同步

原题链接

其实这题不难。考虑直接搜索所有情况，最多有 \(4^{10} = 1048576\) 种可能的走法，因此深搜即可简单解决问题。注意到需要数组的变化，因此，如果要用宽搜的话很可能记录状态不方便（直接内存炸掉？），深搜传数组是个很好的选择。

注意几个点：

• 如果某个方向第一个就是个 block，那么你不可以朝那个方向打然后干掉这个 block，规则是 stone 必须要滑行，不能直接被档在原地。
• 如果 stone 出界就直接失败，而不是停在边界。
• block 被撞倒后会消失。

其实不难。

时间复杂度：\(\mathcal{O(p(n+m))}\)，其中 \(\max_p = 4^{10}\).

#include<cstdio> #include<iostream> using namespace std; inline int read(){char ch=getchar(); int f=1; while(!isdigit(ch)) {if(ch==‘-‘) f=-f; ch=getchar();} int x=0;while(isdigit(ch)) x=x*10+ch-‘0‘,ch=getchar(); return x*f;} int n,m,a[21][21]; int sti,stj,ans; inline void dfs(int a[21][21],int x,int y,int step) { if(step>=ans || step>=10) return; /* printf("%d %d %d\n",x,y,step); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) printf("%d ",a[i][j]); puts(""); } puts("");*/ int xx=x,yy=y; // move left: while(y && a[x][y]==0) y--; if(y && (yy-y>1 || a[x][y]==3)) { if(a[x][y]==3) {ans=min(ans,step+1); return;} a[x][y]=0; dfs(a,x,y+1,step+1); a[x][y]=1; } x=xx,y=yy; // move right: while(y!=m+1 && a[x][y]==0) y++; if(y!=m+1 && (y-yy>1 || a[x][y]==3)) { if(a[x][y]==3) {ans=min(ans,step+1); return;} a[x][y]=0; dfs(a,x,y-1,step+1); a[x][y]=1; } x=xx,y=yy; // move up: while(x && a[x][y]==0) x--; if(x && (xx-x>1 || a[x][y]==3)) { if(a[x][y]==3) {ans=min(ans,step+1); return;} a[x][y]=0; dfs(a,x+1,y,step+1); a[x][y]=1; } x=xx,y=yy; // move down: while(x!=n+1 && a[x][y]==0) x++; if(x!=n+1 && (x-xx>1 || a[x][y]==3)) { if(a[x][y]==3) {ans=min(ans,step+1); return;} a[x][y]=0; dfs(a,x-1,y,step+1); a[x][y]=1; } } int main() { m=read(),n=read(); while(n && m) { ans=19260817; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { a[i][j]=read(); if(a[i][j]==2) sti=i,stj=j,a[i][j]=0; } dfs(a,sti,stj,0); printf("%d\n",ans==19260817?-1:ans); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) a[i][j]=0; m=read(),n=read(); } return 0; }

POJ3009 Curling2.0 题解