第二次做在某個方向上的深搜，第一次做是是杭電oj上的那個連連看，當(dāng)時看了題解也沒看懂，現(xiàn)在這個不看題解也可以搞的出來了，挺高興的。 不過題目的意思還是看的題解，有些地方翻譯不過來。。。。。。
題解：http://blog.csdn.net/lyy289065406/article/details/6647671
#include <cstdio>#include <cstring>#define MAXN 22//網(wǎng)格中1表示石頭，不能走int w,h;int g[MAXN][MAXN];int sx,sy,ex,ey,res;int next[4][2] = {{-1,0},{1,0},{0,-1},{0,1}}; //0 上 1 下 2 左 3 右void dfs(int tx, int ty, int dir, int cnt, int flag){ if(cnt > 10 || cnt > res) return; if(tx == ex && ty == ey) { if(cnt < res) res = cnt; return; } int nx = tx + next[dir][0]; int ny = ty + next[dir][1];//要移動的下一個格子的行號和列號 //先判斷邊界 if(nx < 0 || ny < 0 || nx >= h || ny >= w) return; //再判斷下個格子有沒有石頭 //如果下個格子是石頭，并且冰壺是動態(tài)的，則向其他幾個方向移動 if(g[nx][ny] == 1 && flag) { g[nx][ny] = 0;//石頭被碰掉了 for(int i = 0; i < 4; ++i) { //if(i != dir) dfs(tx,ty,i,cnt+1,flag^1);//碰到石頭了，成靜態(tài)了 } g[nx][ny] = 1; } else if(g[nx][ny] == 1 && !flag)//如果下一個格子是個石頭，并且冰壺是靜態(tài)的，返回 { return; } else//沒有碰到石頭，則繼續(xù)在這個方向移動 { if(!flag)//如果冰壺是靜態(tài)的，狀態(tài)轉(zhuǎn)換為動態(tài) dfs(nx,ny,dir,cnt,flag^1); else dfs(nx,ny,dir,cnt,flag); }}int main(){ while(scanf("%d %d",&w,&h) && w+h) { res = 9999999; for(int i = 0; i < h; ++i) for(int j = 0; j < w; ++j) { scanf("%d",&g[i][j]); if(g[i][j] == 2) { sx = i; sy = j; g[i][j] = 0; } if(g[i][j] == 3) { ex = i; ey = j; g[i][j] = 0; } } for(int i = 0; i < 4; ++i) dfs(sx,sy,i,1,0);//標(biāo)記0用于標(biāo)記冰壺是動態(tài)還是靜態(tài)，靜態(tài)為0，動態(tài)為1 if(res > 10)新聞熱點
疑難解答
