一、题意:给定一个矩形区域,代表冰球场。每个单元格可有四种数值: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<row&&y>=0&&y<column)return true;return false;
}bool IsEnd(int x,int y)
{if(x==ex&&y==ey)return true;return false;
}void Dfs(int x,int y)
{if(steps>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<<dx-dir[i]<<' '<<dy-dir[i+1]<<endl;filed[dx][dy]=1;steps--;}}}}return;
}int main()
{// freopen("in.txt","r",stdin);while(cin>>column>>row,column&&row){for(int i=0;i<row;i++){for(int j=0;j<column;j++){cin>>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<<miniSteps<<endl;elsecout<<-1<<endl;}return 0;
}