车辆调度(dfs+模拟)

题目：车辆调度

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

1.向北走，直到撞到空地的边界、障碍物或其他遥控车；
2.向南走，直到撞到空地的边界、障碍物或其他遥控车；
3.向西走，直到撞到空地的边界、障碍物或其他遥控车；
4.向东走，直到撞到空地的边界、障碍物或其他遥控车；

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

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

输入描述:
第一行输入三个数字w, h, k (1 ≤ w, h ≤ 10, 1 ≤ k ≤ 5) ,含义在题目描述中已给出。

接下来h行，每行输入一个长度为w的字符串si，其中第i行的第j个字符表示(i, j)位置的状态。

其中，'R’代表该位置初始有一辆遥控车，'X’代表该位置有障碍物，‘D’代表该位置是一个目标点，’.'代表该位置可以正常通过。

数据保证广场上的遥控车不超过4辆。

输出描述:
如果k分钟后有可能有任意一个遥控车处在任意一个目标点上，输出YES,否则输出NO。

分析： 由于w, h, k 都很小，因此我们可以用dfs遍历全部情况，这题的难点在于如何更新地图。

#include <bits/stdc++.h>
using namespace std;
const int N=15;
int w,h,k,flag=0;
char a[N][N];
int Next[][2]={{1,0},{-1,0},{0,1},{0,-1}}; //方向数组
bool check(int x,int y){ //判断点(x,y)是否合法
	if(x>=1&&x<=h&&y>=1&&y<=w&&a[x][y]!='R'&&a[x][y]!='X') return true;
	return false;
}
void dfs(int cnt){ //cnt表示当前已有cnt次移动
	

	if(cnt>=k) return ;
	if(flag) return ;
	for(int i=1;i<=h;i++){  //用这种方法就可以更新地图
		for(int j=1;j<=w;j++){
			if(a[i][j]=='R'){ //枚举每一辆小车
				for(int k=0;k<4;k++){
					int tx=i,ty=j;
					while(check(tx+Next[k][0],ty+Next[k][1])){ //不断向这个方向前进
						tx+=Next[k][0]; ty+=Next[k][1];
					}
					if(a[tx][ty]=='D') flag=1; //可以到达D，标记
					swap(a[tx][ty],a[i][j]);   //交换
					dfs(cnt+1);                //向下搜索
					swap(a[tx][ty],a[i][j]);   //交换回来
				}
			}
		}
	}
	
	
	
	
	
	
	
}
int main(){
	

	scanf("%d %d %d",&w,&h,&k);
	for(int i=1;i<=h;i++){
		scanf("%s",a[i]+1);
	}
	

	dfs(0);
	if(flag) printf("YES\n");
	else printf("NO\n");
	
	
	
	
	
	return 0;
}