当前位置: 代码迷 >> 综合 >> POJ3009 Curling 2.0(DFS)
  详细解决方案

POJ3009 Curling 2.0(DFS)

热度:2   发布时间:2024-01-16 13:54:11.0

题意:

冰壶比赛,球会沿着直线一直运动下去,碰到阻碍会停下,同时阻碍消失,求最小步数

要点:

DFS的变种,原本的DFS是一步一步的,现在是沿着直线一直下去,其实差不多,就是把直线看成一步就行。因为可以交错,所以不用设visit数组,同时要用回溯法。因为题目上说超过10步就失败,大大减少了时间复杂度,直接搜索每条路线就可以了。


15196974 Seasonal 3009 Accepted 252K 125MS C++ 999B 2016-02-25 09:51:46
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define judge(x,y) x>=0&&x<m&&y>=0&&y<n&&map[x][y]!=1 //用预处理器函数
int map[150][150];
int d[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };
int m, n;
int step, minstep;void dfs(int x, int y)
{int i;if (step > 10)return;for (i = 0; i < 4; i++){int xx = x + d[i][0];int yy = y + d[i][1];int ok = 0;while (judge(xx,yy))//先一直走到底再考虑dfs的问题{ok = 1;					//用ok来判断是否走了,没走的话直接换方向if (map[xx][yy] == 3)if (minstep > step)//因为这题step有与10比较,而且还要最小,所以设一个minstep求最小minstep = step;xx += d[i][0]; yy += d[i][1];}if (map[xx][yy] == 1 && ok){map[xx][yy] = 0; step++;  //走到底算一步dfs(xx - d[i][0], yy - d[i][1]);map[xx][yy] = 1; step--;  //回溯,因为这道题可以走重复的路}}
}int main()
{int i,j,dx,dy;while (~scanf("%d%d", &n, &m), m + n){memset(map, 0, sizeof(map));for (i = 0; i < m; i++){for (j = 0; j < n; j++){scanf("%d", &map[i][j]);if (map[i][j] == 2){dx = i;dy = j;}}}minstep = 100000; step = 1;dfs(dx, dy);printf("%d\n", minstep>10?-1:minstep);}return 0;
}