首页 > 代码库 > poj 3009 Curling 2.0 【DFS】

poj 3009 Curling 2.0 【DFS】

题意:从2出发,要到达3, 0可以通过,碰到1要停止,并且1处要变成0, 并且从起点开始沿着一个方向要一直前进,直至碰到1(或者3)处才能停止,(就是反射来反射去知道反射经过3).如果反射10次还不能到达3,就输出-1.

策略:深搜。

易错点,方向不容易掌握,并且,出题人把n, m顺序反了。

代码:

#include<stdio.h>
#include<string.h>
int map[25][25];
int ans, n, m;
const int dir[4][2] = {0, -1, 0, 1, 1, 0, -1, 0};//方向
int limit(int x, int y)
{
	return (x>0&&x<=n&&y>0&&y<=m);//注意:x是小于等于m y是小于等于n
}
void dfs(int x, int y, int step)
{
	if(step >= 10) return;
	int i, nx, ny;
	for(i = 0; i < 4; i ++){
		nx = x+dir[i][0];
		ny = y+ dir[i][1];
		if(limit(nx, ny)&&map[nx][ny] != 1){ //判断是不是1,如果不是1,就朝该方向前进
			while(limit(nx, ny)&&map[nx][ny] != 1&&map[nx][ny] != 3){//碰到1或3停止
				nx += dir[i][0];
				ny += dir[i][1];
			}
			if(map[nx][ny] == 3){
				if(ans > step+1){
					ans = step+1;
				}
				return;//碰到3就停止
			}
			else if(map[nx][ny] == 1){
				map[nx][ny] = 0;
				dfs(nx-dir[i][0], ny-dir[i][1], step+1);
				map[nx][ny] = 1;
			}
		}
	}
}
int main()
{
	int i, j, sx, sy;
	while(scanf("%d%d", &m, &n), n||m){
		memset(map, 0, sizeof(map));//一定要初始化啊,此处贡献了n个wa
		for(i = 1; i <= n; i ++){
			for(j = 1; j <= m; j ++){
				scanf("%d", &map[i][j]);
				if(map[i][j] == 2){//找到2点的坐标
					sx = i;
					sy = j;
				}
			}
		}	
		ans = 0x3f3f3f3f;//初始化
		dfs(sx, sy, 0);
		if(ans > 10){
			printf("-1\n");
		}
		else{
			printf("%d\n", ans);
		}
	}
} 
题目链接:http://poj.org/problem?id=3009