题意:
冰壶比赛,球会沿着直线一直运动下去,碰到阻碍会停下,同时阻碍消失,求最小步数
要点:
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;
}