模拟就行。题目的意思是找最短的路，但是每次地图都要改变。开始用bfs，把地图保存下来，自然tle了。题目的意思不超过10步。所以可以dfs把所有的可行解找出来，求最少步数。

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5 #include 
          
             6   7 using namespace std;  8   9 #define MAXN 21 10 int map[MAXN][MAXN]; 11 int w,h; 12 int ans; 13  14 struct pos 15 { 16     int x,y; 17 }; 18 pos st; 19 int move(int dir,int step,pos & tmp) 20 { 21     switch(dir) 22     { 23         case 1: 24             if(st.x-1<0 || map[st.x-1][st.y]==1) 25                 return 0; 26             st.x--; 27             while(st.x>=0) 28             { 29                 if(map[st.x][st.y]==3) 30                 { 31                     if(ans>step) 32                         ans=step; 33                     return 1; 34                 } 35                 if(map[st.x][st.y]==1) 36                 { 37                     tmp=st; 38                     map[st.x][st.y]=0; 39                     st.x++; 40                     return 2; 41                 } 42                 st.x--; 43             } 44             return 0; 45             break; 46         case 2: 47             if(st.x+1>=h || map[st.x+1][st.y]==1) 48                 return 0; 49             st.x++; 50             while(st.x
           
            step) 55 ans=step; 56 return 1; 57 } 58 if(map[st.x][st.y]==1) 59 { 60 tmp=st; 61 map[st.x][st.y]=0; 62 st.x--; 63 return 2; 64 } 65 st.x++; 66 } 67 return 0; 68 break; 69 case 3: 70 if(st.y-1<0 || map[st.x][st.y-1]==1) 71 return 0; 72 st.y--; 73 while(st.y>=0) 74 { 75 if(map[st.x][st.y]==3) 76 { 77 if(ans>step) 78 ans=step; 79 return 1; 80 } 81 if(map[st.x][st.y]==1) 82 { 83 tmp=st; 84 map[st.x][st.y]=0; 85 st.y++; 86 return 2; 87 } 88 st.y--; 89 } 90 return 0; 91 break; 92 case 4: 93 if(st.y+1>w || map[st.x][st.y+1]==1) 94 return 0; 95 st.y++; 96 while(st.y
            
             step)101 ans=step;102 return 1;103 }104 if(map[st.x][st.y]==1)105 {106 tmp=st;107 map[st.x][st.y]=0;108 st.y--;109 return 2;110 }111 st.y++;112 }113 return 0;114 break;115 }116 }117 void dfs(int step)118 {119 if(step==10) return ;120 for(int k=1;k<=4;k++)121 {122 pos pre,tmp;123 pre.x=st.x;pre.y=st.y;124 if(move(k,step+1,tmp)==2)125 {126 dfs(step+1);127 map[tmp.x][tmp.y]=1;128 }129 st.x=pre.x;st.y=pre.y;130 }131 132 }133 int main()134 {135 while(scanf("%d%d",&w,&h))136 {137 if(!w && !h) break;138 for(int i=0;i