车辆调度 D题 科大讯飞杯”第十七届同济大学程序设计预选赛暨高校网络友谊赛

“科大讯飞杯”第十七届同济大学程序设计预选赛暨高校网络友谊赛

D题
车辆调度

• 数据量很小10x10,直接dfs
• 搜索树深度<=5,每一层枚举每辆车向4个方向走的方案
• 当递归深度==K时判断是否有车停在目标点

#define debug
#ifdef debug
#include <time.h>
#include "/home/majiao/mb.h"
#endif
 
 
#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <map>
#include <set>
#include <stack>
#include <queue>
#define MAXN ((int)1e5+7)
#define ll long long int
#define QAQ (0)
#include <sstream>
 
using namespace std;
 
int n, m, K;
int dr[] = { 1, -1, 0, 0 }; //4个方向
int dc[] = { 0, 0, 1, -1 };
char mtx[16][16], tmp[16][16]/*用来模拟车的位置(0没有车,1有车)*/;
struct Node {
    int r, c;
} ;
 
bool check(int x, int y) { //判断是否越界
    return mtx[x][y];
}
 
bool ok = false;
void dfs(int level, vector<Node> v) {
    if(ok) return ;
    if(level == K) { //第level步恰好有在目标格子的车就ok=true
        for(int i=1; i<=n; i++)
            for(int k=1; k<=m; k++)
                if(tmp[i][k] && mtx[i][k]=='D') {
                    ok = true;
                    goto p;
                }
        p:
        return ;
    }
    for(int i=0; i<int(v.size()) && !ok; i++) { //枚举每辆车
        Node& no = v[i];
        //每辆车都有4个方向
        for(int k=0; k<4 && !ok; k++) {
            int tmpr = no.r, tmpc = no.c;
 
            //移动到这个方向,直到撞墙或撞车
            while(check(no.r+dr[k], no.c+dc[k]) &&
                    (mtx[no.r+dr[k]][no.c+dc[k]]!='X')
                    && !(tmp[no.r+dr[k]][no.c+dc[k]])) {
                no.r += dr[k], no.c += dc[k];
            }
            tmp[no.r][no.c] = true;
            tmp[tmpr][tmpc] = false;
            dfs(level+1, v); //递归下一步
            tmp[no.r][no.c] = false; //还原现场
            tmp[tmpr][tmpc] = true;
            no.r = tmpr, no.c = tmpc;
        }
    }
}
 
int main() {
#ifdef debug
    freopen("test", "r", stdin);
    clock_t stime = clock();
#endif
    scanf("%d %d %d ", &m, &n, &K);
    vector<Node> vec;
    for(int i=1; i<=n; i++) {
        scanf("%s ", mtx[i]+1);
        for(int k=1; k<=m; k++)
            if(mtx[i][k] == 'R') vec.push_back({i, k});
    }
    dfs(0, vec);
    printf("%s\n", ok ? "YES" : "NO");
 
 
 
#ifdef debug
    clock_t etime = clock();
    printf("rum time: %lf 秒\n",(double) (etime-stime)/CLOCKS_PER_SEC);
#endif
    return 0;
}