1 #include <algorithm>  2 #include <iostream>  3 #include <sstream>  4 #include <cstdlib>  5 #include <cstring>  6 #include <cstdio>  7 #include <string>  8 #include <bitset>  9 #include <vector> 10 #include <queue> 11 #include <stack> 12 #include <cmath> 13 #include <list> 14 #include <map> 15 #include <set> 16 using namespace std; 17 /*10^8-----1s*/ 18 /***************************************/ 19 typedef vector<int> VI; 20 typedef vector<char> VC; 21 typedef vector<string> VS; 22 typedef set<int> SI; 23 typedef set<string> SS; 24 typedef map<int ,int> MII; 25 typedef map<string,int> MSI; 26 typedef pair<int,int> PII; 27 typedef vector<PII> VII; 28 typedef vector<VI > VVI; 29 /***************************************/ 30 #define min(a,b) (a>b?b:a) 31 #define max(a,b) (a>b?a:b) 32  33 #define clr(a,b) memset(a,b,sizeof(a)) 34 #define all(x)    (x).begin(), (x).end() 35 #define sz(x) ((int)(x).size()) 36 #define ll long long 37 #define int64 __int64 38 #define pb push_back 39 #define mp make_pair 40 #define LL(x) ((x)<<1) 41 #define RR(x) ((x)<<1|1) 42 #define ri(x) scanf("%d",&x) 43 #define rii(x,y) scanf("%d%d",&x,&y) 44 #define rd(x) scanf("%lf",&x) 45 #define rdd(x,y) scanf("%lf%lf",&x,&y) 46 #define rs(x) scanf("%s",x) 47 #define pi(x) printf("%d",x) 48 #define pin(x) printf("%d\n",x) 49 #define ps(x) printf("%s",x) 50 #define pn()  printf("\n") 51 #define sqr(x) ((x)*(x)) 52 #define rep(i,a,b)  for(int i=(a);i<(b);i++) 53 #define repu(i,a,b) for(int i=(a);i<=(b);i++) 54 #define repd(i,a,b) for(int i=(a);i>=(b);i--) 55 #define repc(i,a,c) for(int i=(a);(c);i++) 56 /***************************************/ 57 const int INF = 0x7f7f7f7f; 58 const double eps = 1e-8; 59 const double PIE=acos(-1.0); 60 const int dx[]= {0,-1,0,1}; 61 const int dy[]= {1,0,-1,0}; 62 const int fx[]= {-1,-1,-1,0,0,1,1,1}; 63 const int fy[]= {-1,0,1,-1,1,-1,0,1}; 64 /***************************************/ 65 void openfile() 66 { 67     freopen("data.in","rb",stdin); 68     freopen("data.out","wb",stdout); 69 } 70 /**********************The End OF The Template*****************/ 71  72 //dfs+回溯+剪枝 73 int x,y; 74 int a[22][22]; 75 int max_step; 76 void dfs(int xx,int yy,int step,int peng,int fx) 77 { 78     if(step>10) 79         return ; 80     if(a[xx][yy]==3) 81     { 82         max_step=min(max_step,step); 83         return ; 84     } 85  86     if(peng&&step!=0)//表明下一个格是1，让其消失，处理现场 87     { 88         //目前小球  运动的方向   上1 下2 左3 右4 89         if(fx==1) 90             a[xx-1][yy]=0; 91         else if(fx==2) 92             a[xx+1][yy]=0; 93         else if(fx==3) 94             a[xx][yy-1]=0; 95         else if(fx==4) 96             a[xx][yy+1]=0; 97     } 98  99 100     /***********************************************************/101 102 //从一个静止状态到下一个静止状态103 //就是说小球在运动时经过的“格数”不视作“步数”104 //也就是说冰壶每次移动的距离都是不定的105 106     if(peng)//下一个格为小球，要碰，要改变方向，转弯107     {108         if(xx-1>=0&&a[xx-1][yy]!=1)109             dfs(xx-1,yy,step+1,0,1);110         if(xx+1<x&&a[xx+1][yy]!=1)111             dfs(xx+1,yy,step+1,0,2);112         if(yy-1>=0&&a[xx][yy-1]!=1)113             dfs(xx,yy-1,step+1,0,3);114         if(yy+1<y&&a[xx][yy+1]!=1)115             dfs(xx,yy+1,step+1,0,4);116     }117     else//直走 不会碰  就直走  并不算步数里面118     {119         if(fx==1)120         {121             if(xx-1>=0)122             {123                 if(a[xx-1][yy]==1) // 下一个格是雪球，即应停止（peng=1）124                     dfs(xx,yy,step,1,fx);125                 else126                     dfs(xx-1,yy,step,0,fx);127             }128         }129         else if(fx==2)130         {131             if(xx+1<x)132             {133                 if(a[xx+1][yy]==1)134                     dfs(xx,yy,step,1,fx);135                 else136                     dfs(xx+1,yy,step,0,fx);137             }138         }139         else if(fx==3)140         {141             if(yy-1>=0)142             {143                 if(a[xx][yy-1]==1)144                     dfs(xx,yy,step,1,fx);145                 else146                     dfs(xx,yy-1,step,0,fx);147             }148         }149         else if(fx==4)150         {151             if(yy+1<y)152             {153                 if(a[xx][yy+1]==1)154                     dfs(xx,yy,step,1,fx);155                 else156                     dfs(xx,yy+1,step,0,fx);157             }158         }159     }160 161     /*********************************************************/162     if(peng&&step!=0)//回溯，现场还原163     {164         if(fx==1)165             a[xx-1][yy]=1;166         else if(fx==2)167             a[xx+1][yy]=1;168         else if(fx==3)169             a[xx][yy-1]=1;170         else if(fx==4)171             a[xx][yy+1]=1;172     }173 174 }175 176 177 178 int main()179 {180     int jii,jij;181     int i,j;182     while(scanf("%d %d",&y,&x)&&(x&&y))183     {184         max_step=INF;185         for(i=0; i<x; i++)186             for(j=0; j<y; j++)187             {188                 scanf("%d",&a[i][j]);189                 if(a[i][j]==2)190                 {191                     jii=i;192                     jij=j;193                 }194             }195         a[jii][jij]=0;196         dfs(jii,jij,0,1,1);197         if(max_step==INF)198             printf("-1\n");199         else200             printf("%d\n",max_step);201     }202     return 0;203 }