poj3009 Curling 2.0（很好的题 DFS）

 1 #include<iostream> 2 #include<cstdio> 3 #include<queue> 4 #include<cstring> 5 #include<algorithm> 6 #include<cmath> 7 #include<stack> 8 #define lson l, m, rt<<1 9 #define rson m+1, r, rt<<1|110 #define IO ios::sync_with_stdio(false);cin.tie(0);11 #define INF 0x3f3f3f3f12 typedef unsigned long long ll;13 using namespace std;14 int n, m, mp[30][30], si, sj, gi, gj, cnt, mini;15 int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};16 void dfs(int x, int y, int a, int b, int k, int c)17 {18 ????if(k > 10||k > mini) return ;19 ????if(x == gi&&y == gj){20 ????????mini = min(mini, k); 21 ????????return ;22 ????}23 ????if(a != 0||b != 0){//不是刚开始 24 ????????if(x<0||x>=n||y<0||y>=m){25 ????????????return;//失败 26 ????????}27 ????????else if(mp[x][y] == 1){28 ????????????if(c <= 1) return ;29 ????????????c = 0;30 ????????????mp[x][y] = 0;//该阻被消去 31 ????????????x -= a;32 ????????????y -= b;//回到上一状态 33 ????????????for(int i = 0; i < 4; i++){34 ????????????????dfs(x+dir[i][0], y+dir[i][1], dir[i][0], dir[i][1], k+1, c+1);35 ????????????}36 ????????????x += a;37 ????????????y += b;38 ????????????mp[x][y] = 1;//记住要状态复原！！ 39 ????????}40 ????????else{41 ????????????dfs(x+a, y+b, a, b, k, c+1);42 ????????}43 ????}44 ????else{ 45 ????????for(int i = 0; i < 4; i++){46 ????????????dfs(x+dir[i][0], y+dir[i][1], dir[i][0], dir[i][1], k+1, c+1);47 ????????} 48 ????}49 }50 int main()51 {52 ????while(cin >> m >> n, n, m){53 ????????mini = INF;54 ????????cnt=0;55 ????????for(int i = 0; i < n; i++){56 ????????????for(int j = 0; j < m; j++){57 ????????????????cin >> mp[i][j];58 ????????????????if(mp[i][j] == 2) si=i,sj=j;59 ????????????????if(mp[i][j] == 3) gi=i,gj=j;60 ????????????}61 ????????}62 ????????dfs(si, sj, 0, 0, 0, 0);63 ????????if(mini == INF) cout << "-1" << endl;64 ????????else cout << mini << endl;65 ????}66 ????return 0;67 }