第十七届“科大讯飞杯” D 车辆调度 题解

题目大意

张老师设计了一个智能调度系统来控制他的遥控车队，今天，他带着他的车队来到黄渡理工大学的一块空地上测试这个系统。
这块空地可以描述为一个 w * h 大小的长方形，广场上有一些障碍物，几个目标点，当然，还有张老师的车队。
每分钟，调度系统会智能地向其中的一辆遥控车发送以下指令的其中一条：

1. ​ 向北走，直到撞到空地的边界、障碍物或其他遥控车；

2. ​ 向南走，直到撞到空地的边界、障碍物或其他遥控车；

3. ​ 向西走，直到撞到空地的边界、障碍物或其他遥控车；

4. ​ 向东走，直到撞到空地的边界、障碍物或其他遥控车；

   ​ 每条指令都会在一分钟之内完成，也就是说，空地上最多只有一辆遥控车在运动。此外，当遥控车无法向相应的方向移动时，它会停在原地。

   你想知道，在第 k 分钟时，有没有可能有任意一辆遥控车处在任意一个目标点上。

解题思路

很明显的搜索，模拟这个车的行动。

（但是。。我真的不是很会搜索。。

其实想到了DFS但是没想到怎么去模拟，卡了半天。

（还是需要再去学一下。。刚开始学的时候可能没学懂。

其实BFS也是可以的。。不想写了

完整代码

#include <iostream>
using namespace std;

char Map[20][20];
int n, m, k, flag;
int dx[5] = { 0,0,-1,1 }, dy[5] = { -1,1,0,0 };

int check(int x, int y) {
	if (x < 1 || x > n || y < 1 || y > m || Map[y][x] == 'X' || Map[y][x] == 'R')	return 0;
	return 1;
}

void dfs(int t) {
	if (t >= k)	return;//搜索步数，这点永远想不到。。
	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= n; j++) {
			if (Map[i][j] == 'R') {
				for (int g = 0; g < 4; g++) {
					int x = j, y = i;
					while (check(x + dx[g], y + dy[g]))	x += dx[g], y += dy[g];
					if (Map[y][x] == 'D')	flag = 1;
					if (flag)	return;
					swap(Map[i][j], Map[y][x]);
					dfs(t + 1);
					swap(Map[i][j], Map[y][x]);//注意还原，也经常想不到
				}
			}
		}
	}
}

int main() {
	cin >> n >> m >> k;
	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> Map[i][j];
		}
	}
	flag = 0;
	dfs(0);
	if (flag)	cout << "YES" << endl;
	else cout << "NO" << endl;
}