NC206019. 车辆调度
描述
张老师设计了一个智能调度系统来控制他的遥控车队，今天，他带着他的车队来到黄渡理工大学的一块空地上测试这个系统。
这块空地可以描述为一个 w * h 大小的长方形，广场上有一些障碍物，几个目标点，当然，还有张老师的车队。
每分钟，调度系统会智能地向其中的一辆遥控车发送以下指令的其中一条：
向北走，直到撞到空地的边界、障碍物或其他遥控车；
向南走，直到撞到空地的边界、障碍物或其他遥控车；
向西走，直到撞到空地的边界、障碍物或其他遥控车；
向东走，直到撞到空地的边界、障碍物或其他遥控车；
每条指令都会在一分钟之内完成，也就是说，空地上最多只有一辆遥控车在运动。此外，当遥控车无法向相应的方向移动时，它会停在原地。
你想知道，在第 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。
示例1
输入:
6 5 4 .....R ...X.. ..D... ....D. R.R...
输出:
YES
说明:
样例中，遥控车可以按下述路线移动：
.....R
...X..
..D...
....D.
R.....
...X..
..D...
....D.
R.....
R..X..
..D...
....D.
R.....
..RX..
..D...
....D.
R.....
..RX..
..R...
....D.
......
4分钟时，有一辆遥控车达到了目标点。于是输出YES
C++14(g++5.4) 解法, 执行用时: 38ms, 内存消耗: 476K, 提交时间: 2020-05-11 10:23:22
#include<bits/stdc++.h>
using namespace std;
const int N=15;
char mp[N][N];
int ok,w,h,k,d[4][2]={0,1,0,-1,1,0,-1,0};
bool ck(int x,int y){
if(x>=1&&x<=h&&y>=1&&y<=w&&mp[x][y]!='R'&&mp[x][y]!='X') return 1;
return 0;
}
void dfs(int cnt){
if(cnt>=k) return;
for(int i=1;i<=h;i++)
for(int j=1;j<=w;j++)
if(mp[i][j]=='R')
for(int l=0;l<4;l++){
int nx=i,ny=j;
while(ck(nx+d[l][0],ny+d[l][1]))
nx+=d[l][0],ny+=d[l][1];
if(mp[nx][ny]=='D'){
ok=1;
}
if(ok) break;
swap(mp[nx][ny],mp[i][j]);
dfs(cnt+1);
swap(mp[nx][ny],mp[i][j]);
}
}
int main(){
scanf("%d%d%d",&w,&h,&k);
for(int i=1;i<=h;i++) scanf("%s",mp[i]+1);
dfs(0);
puts(ok?"YES":"NO");
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 45ms, 内存消耗: 476K, 提交时间: 2020-07-02 14:25:39
#include<bits/stdc++.h>
using namespace std;
int i,n,m,t,dx[]={1,-1,0,0},dy[]={0,0,1,-1};
char R[15][15];
void DFS(int s)
{
if(s==t)return;
int i,j,k,l,X,Y;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
if(R[i][j]!='R')continue;
for(k=0;k<4;k++)
{
X=i+dx[k],Y=j+dy[k];
while(X&&X<=n&&Y&&Y<=m&&R[X][Y]!='R'&&R[X][Y]!='X')X+=dx[k],Y+=dy[k];
X-=dx[k],Y-=dy[k];
if(R[X][Y]=='D'){printf("YES\n");exit(0);}
swap(R[i][j],R[X][Y]);
DFS(s+1);
swap(R[i][j],R[X][Y]);
}
}
}
int main()
{
scanf("%d%d%d",&m,&n,&t);
for(i=1;i<=n;i++)scanf("%s",R[i]+1);
DFS(0);
printf("NO\n");
return 0;
}