首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。