題目大意要求把一個冰壺從起點“2”用最少的步數移動到終點“3”
其中0為移動區域,1為石頭區域,冰壺一旦想著某個方向運動就不會停止,也不會改變方向(想想冰壺在冰上滑動),除非冰壺撞到石頭1 或者 到達終點 3
冰壺撞到石頭後,冰壺會停在石頭前面,此時(靜止狀態)才允許改變冰壺的運動方向,而該塊石頭會破裂,石頭所在的區域由1變為0. 也就是說,冰壺撞到石頭後,並不會取代石頭的位置。
終點是一個摩擦力很大的區域,冰壺若到達終點3,就會停止在終點的位置不再移動。
要先明確:
0為滑動區域
1為石頭區域
2為起點,也是可滑動區域
3為終點,不可滑動區域
#includeusing namespace std; struct SE { int r, c; bool status; }s, e; int w, h; int MinStep; int board[30][30]; void DFS(int i, int j, bool status, int direction, int step, bool flag) { //direction:冰壺當前運動方向 North:0 West:1 South:2 East:3 //flag:是否消除direction方向下一格位置的石頭 if(step>10) return; if(board[i][j]==3) { if(MinStep>step) MinStep=step; return; } if(flag) { switch(direction) { case 0:{board[i-1][j]=0;break;} case 1:{board[i][j-1]=0;break;} case 2:{board[i+1][j]=0;break;} case 3:{board[i][j+1]=0;break;} } } if(!status) //靜止 { if(i-1>=1 && (board[i-1][j]==0 || board[i-1][j]==3)) //North DFS(i-1,j,true,0,step+1,false); if(j-1>=1 && (board[i][j-1]==0 || board[i][j-1]==3)) //West DFS(i,j-1,true,1,step+1,false); if(i+1<=h && (board[i+1][j]==0 || board[i+1][j]==3)) //South DFS(i+1,j,true,2,step+1,false); if(j+1<=w && (board[i][j+1]==0 || board[i][j+1]==3)) //East DFS(i,j-1,true,3,step+1,false); } else if(status) //運動 { switch(direction) { case 0: { if(i-1<1) //預判下一步是否越界 return; else { if(board[i-1][j]==0) //下一位置為0且不越界,繼續運動 DFS(i-1,j,true,0,step,false); else if(board[i-1][j]==1) //下一位置為1且不越界,停止運動,並消除下一位置的石頭 DFS(i,j,false,0,step,true); else if(board[i-1][j]==3) //下一位置為3且不越界,運動到位置3後停止運動,游戲結束 DFS(i-1,j,false,0,step,false); } break; } case 1: { if(j-1<1) //預判下一步是否越界 return; else { if(board[i][j-1]==0) //下一位置為0且不越界,繼續運動 DFS(i,j-1,true,1,step,false); else if(board[i][j-1]==1) //下一位置為1且不越界,停止運動,並消除下一位置的石頭 DFS(i,j,false,1,step,true); else if(board[i][j-1]==3) //下一位置為3且不越界,運動到位置3後停止運動,游戲結束 DFS(i,j-1,false,1,step,false); } break; } case 2: { if(i+1>h) //預判下一步是否越界 return; else { if(board[i+1][j]==0) //下一位置為0且不越界,繼續運動 DFS(i+1,j,true,2,step,false); else if(board[i+1][j]==1) //下一位置為1且不越界,停止運動,並消除下一位置的石頭 DFS(i,j,false,2,step,true); else if(board[i+1][j]==3) //下一位置為3且不越界,運動到位置3後停止運動,游戲結束 DFS(i+1,j,false,2,step,false); } break; } case 3: { if(j+1>w) //預判下一步是否越界 return; else { if(board[i][j+1]==0) //下一位置為0且不越界,繼續運動 DFS(i,j+1,true,3,step,false); else if(board[i][j+1]==1) //下一位置為1且不越界,停止運動,並消除下一位置的石頭 DFS(i,j,false,3,step,true); else if(board[i][j+1]==3) //下一位置為3且不越界,運動到位置3後停止運動,游戲結束 DFS(i,j+1,false,3,step,false); } break; } } } if(flag) //回溯前還原石頭,即還原上一步的棋盤狀態 { switch(direction) { case 0: {board[i-1][j]=1; break;} case 1: {board[i][j-1]=1; break;} case 2: {board[i+1][j]=1; break;} case 3: {board[i][j+1]=1; break;} } } return; } int main(void) { while(cin>>w>>h) { if(!w && !h) break; /*Structure the Board*/ MinStep=11; for(int i=1;i<=h;i++) for(int j=1;j<=w;j++) { cin>>board[i][j]; if(board[i][j]==2) { s.r=i; s.c=j; s.status=false; board[i][j]=0; //記錄起點位置後,把它作為0處理 } if(board[i][j]==3) //終點是特別位置,冰壺經過或到達該格都會停止 { e.r=i; e.c=j; } } DFS(s.r , s.c , s.status , 0 , 0 , false); if(MinStep<=10) cout<