题意：溜石游戏。在一给定大小的矩形冰面上，散布若干石块，给定石头的初始位置和终点，求从起点到达终点的最小步数，超过10次则视作不可达。其中规则如下，若石头与石块有相邻则不能向该方向滑动；每次溜石只能到达有石块的地方，且将其立即敲碎；若出界则视作失败。思路：限制条件较多的dfs，每个状态下有四个方向的选择，注意每个滑动方向中的情况，较繁琐。#include#include const int inf=999999;using namespace std;int r,c,step,sx,sy,ex,ey;int inmap(int x,int y){ if(x>=1&&x<=r&&y>=1&&y<=c)return 1; else return 0;}void dfs(int x,int y,int num,int map[][30]){ int i,j,k; if(num>10)return;//注意这的终止条件，我就tle 一次 i=x; j=y; k=num; while(map[i][j+1]==0&&inmap(i,j+1))//向右 { j++; } if(inmap(i,j+1)&&map[x][y+1]!=1) { k++; if(i==ex&&j+1==ey) { step=min(step,k); return ; } map[i][j+1]=0; dfs(i,j,k,map); map[i][j+1]=1; } i=x; j=y; k=num; while(map[i+1][j]==0&&inmap(i+1,j))//向下 { i++; } if(inmap(i+1,j)&&map[x+1][y]!=1) { k++; if(i+1==ex&&j==ey) { step=min(step,k); return ; } map[i+1][j]=0; dfs(i,j,k,map); map[i+1][j]=1; } i=x; j=y; k=num; while(map[i][j-1]==0&&inmap(i,j-1))//向左 { j--; } if(inmap(i,j-1)&&map[x][y-1]!=1) { k++; if(i==ex&&j-1==ey) { step=min(step,k); return ; } map[i][j-1]=0; dfs(i,j,k,map); map[i][j-1]=1; } i=x; j=y; k=num; while(map[i-1][j]==0&&inmap(i-1,j))//向上 { i--; } if(inmap(i-1,j)&&map[x-1][y]!=1) { k++; if(i-1==ex&&j==ey) { step=min(step,k); return ; } map[i-1][j]=0; dfs(i,j,k,map); map[i-1][j]=1; }}int main(){ int map[30][30],i,j; while(scanf("%d%d",&c,&r),r+c) { for(i=1;i<=r;i++) { for(j=1;j<=c;j++) { scanf("%d",&map[i][j]); if(map[i][j]==2) { sx=i; sy=j; map[i][j]=0; } if(map[i][j]==3) { ex=i; ey=j; } } } step=inf; dfs(sx,sy,0,map); if(step!=inf&&step<=10) printf("%d\n",step); else printf("-1\n"); }}