| ||||||||||
| 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