当前位置: 代码迷 >> 综合 >> poj-3009-Curling 2.0-dfs
  详细解决方案

poj-3009-Curling 2.0-dfs

热度:17   发布时间:2023-12-19 11:27:21.0

终于A了,一上午就A了一道题目,好没有成就感·········

题意:

溜石游戏。在一给定大小的矩形冰面上,散布若干石块,给定石头的初始位置和终点,求从起点到达终点的最小步数,超过10次则视作不可达。其中规则如下,若石头与石块有相邻则不能向该方向滑动;每次溜石只能到达有石块的地方,且将其立即敲碎;若出界则视作失败。

做法:

对每一步到达的终点进行四个方向的搜索,直至搜到3或者搜索结束。

注意:

1,当搜索的步数大于10的时候,要终止搜索。

2,当在滑动过程中搜索到3的话,也要终止。

3,不要对图进行标记,因为搜索的方向是四个方向。标记会出错。

4,在标记完起点的位置后,记得把起点的置置为0;

#include<iostream>
#include<stdio.h>
#include<String.h>
#define MIN(a,b) (a>b?b:a)
#define pan(a,b,c) (a<=c&&c<=b)
using namespace std;
int map[101][101];
int st;
int xx[4]={-1,0,1,0};
int yy[4]={0,1,0,-1};
int n,m;
int maxs;
void dfs(int x,int y,int z)
{int i,leap,dx,dy;if(z>10)return ;for(i=0;i<4;i++){if(map[x+xx[i]][y+yy[i]]==1)continue;leap=0;dx=x;dy=y;while(1){dx=dx+xx[i];dy=dy+yy[i];if(!(pan(1,n,dx)&&pan(1,m,dy))){leap=1;break;}if(map[dx][dy]==0)continue;else if(map[dx][dy]==1)break;else if(map[dx][dy]==3){maxs=MIN(maxs,z);return ;}}if(leap)continue;map[dx][dy]=0;dfs(dx-xx[i],dy-yy[i],z+1);map[dx][dy]=1;}
}
int main()
{int i,j,a;int st_x,st_y;while(scanf("%d%d",&m,&n)&&(m||n)){maxs=11;memset(map,0,sizeof(map));for(i=1;i<=n;i++){for(j=1;j<=m;j++){scanf("%d",&a);map[i][j]=a;if(a==2){st_x=i;st_y=j;map[i][j]=0;}}}dfs(st_x,st_y,0);if(maxs+1<11)printf("%d\n",maxs+1);elseprintf("-1\n");}return 0;
}