一、题意：给定一个矩形区域，代表冰球场。每个单元格可有四种数值：2是冰球的起始位置；3代表冰球最后需要到达的位置；0代表空，球可通过；1代表障碍物，球碰撞一次后，1变成0，球停在1前面那个位置。球只能上下左右移动（一次朝一个方向移动直至碰到1或者3或者出界为止）。求球从2到3的最短步数（必须小于等于10才算），没有则输出-1；

 

二、思路：遍历球可走的所有情况，找出最短路径。这里需要注意的是步数的回溯。

 

三、代码：

#include"iostream"#include"stdio.h"#include"istream"using namespace std;const int MAXN=25;int filed[MAXN][MAXN];int column,row,sx,sy,ex,ey,steps,miniSteps;bool IsEdge(int x,int y){    if(x>=0&&x
     
      =0&&y
      
       10) return;    int dir[8]={0,1,0,-1,1,0,-1,0};    for(int i=0;i<8;i+=2)    {        int dx=x+dir[i];        int dy=y+dir[i+1];        if(IsEdge(dx,dy))        {            if(IsEnd(dx,dy))            {                 steps++;                 if(miniSteps>steps)                    miniSteps=steps;                 steps--;                 return;            }            else if(filed[dx][dy]==0)            {                while(IsEdge(dx,dy)&&filed[dx][dy]==0)                {                    dx+=dir[i];                    dy+=dir[i+1];                }                if(IsEdge(dx,dy))                {                    if(IsEnd(dx,dy))                    {                          steps++;                          if(miniSteps>steps)                            miniSteps=steps;                          steps--;                          return;                    }                    steps++;                    filed[dx][dy]=0;                    Dfs(dx-dir[i],dy-dir[i+1]);                 //   cout<
       
        <<' '<
        
         <
         
          >column>>row,column&&row)    {        for(int i=0;i
          
           >filed[i][j]; if(filed[i][j]==2) { sx=i;sy=j; } if(filed[i][j]==3) { ex=i;ey=j; } } } steps=0; miniSteps=11; filed[sx][sy]=0; Dfs(sx,sy); if(miniSteps<=10) cout<
           
            <