Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:纠结啊。。。。。改不来了。。。。牛哥们帮忙看看

Posted by 4053040 at 2010-03-07 09:28:13 on Problem 3009
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator