Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:纠结啊。。。。。改不来了。。。。牛哥们帮忙看看In Reply To:纠结啊。。。。。改不来了。。。。牛哥们帮忙看看 Posted by:vince4053040 at 2010-03-07 08:51:32 #include<iostream> using namespace std; #define MAX_N 22 int map[MAX_N][MAX_N]; int answer, sign; int R, C; void dfs(int row, int col, int step, int dir) { cout << row << " " << col << endl; if(dir == 0) { dfs(row, col, step, 1); dfs(row, col, step, 2); dfs(row, col, step, 3); dfs(row, col, step, 4); } int i, j; if(row <= 0 || row > R || col <= 0 || col > C || step > 10) return ; if(map[row][col] == 3) { sign = 1; answer = step; return ; } if(dir == 1) { for(i = row; i > 0; i --) { if(map[i][col] == 3) { sign = 1; answer = step + 1; return ; } if(map[i][col] == 1) { map[i][col] = 0; dfs(i + 1, col, step + 1, 1); dfs(i + 1, col, step + 1, 2); dfs(i + 1, col, step + 1, 3); dfs(i + 1, col, step + 1, 4); map[i][col] = 1; //回溯 step --; break; //忘break了..... } } if(i <= 0) return ; if(step > 10) return ; } if(dir == 2) { for(j = col; j > 0; j --) { if(map[row][j] == 3) { sign = 1; answer = step + 1; return ; } if(map[row][j] == 1) { map[row][j] = 0; dfs(row, j + 1, step + 1, 1); dfs(row, j + 1, step + 1, 2); dfs(row, j + 1, step + 1, 3); dfs(row, j + 1, step + 1, 4); map[row][j] = 1; step --; break; } } if(j <= 0) return ; if(step > 10) return ; } if(dir == 3) { for(i = row; i <= R; i ++) { if(map[i][col] == 3) { sign = 1; answer = step + 1; return ; } if(map[i][col] == 1) { map[i][col] = 0; dfs(i - 1, col, step + 1, 1); dfs(i - 1, col, step + 1, 2); dfs(i - 1, col, step + 1, 3); dfs(i - 1, col, step + 1, 4); map[i][col] = 1; step --; break; } } if(i > R) return ; if(step > 10) return ; } if(dir == 4) { for(j = col; j <= C; j ++) { if(map[row][j] == 3) { sign = 1; answer = step + 1; return ; } if(map[row][j] == 1) { map[row][j] = 0; dfs(row, j - 1, step + 1, 1); dfs(row, j - 1, step + 1, 2); dfs(row, j - 1, step + 1, 3); dfs(row, j - 1, step + 1, 4); map[row][j] = 1; step --; break; } } if(j > C) return ; if(step > 10) return ; } return ; } int main() { int i, j; while(cin >> C >> R && C) { memset(map, 0, sizeof(map)); answer = -1; sign = 0; for(i = 1; i <= R; i ++) for(j = 1; j <= C; j ++) cin >> map[i][j]; for(i = 1; i <= R; i ++) for(j = 1; j <= C; j ++) if(map[i][j] == 2) { dfs(i, j, 0, 0); break; } if(sign == 1) cout << answer << endl; else cout << -1 << endl; } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator