车辆调度

因为数据很小，我们都意识到了暴力搜索，DFS可以更简单地解决。

这题的主要难点在于编码难度，我在写这道题的时候认为每搜索一次重新开辟一个二维数组太蠢，又没想清楚如何动态管理车辆的位置信息，其实不需要管理车辆信息，每次重新搜索就可以了。

详细注释：

#include <bits/stdc++.h>
using namespace std;
const int N = 15;
const int inf = 0x3f3f3f3f;
char mp[N][N];
int dx[] = {0, 0, -1, 1};//合起来分别对应上下左右
int dy[] = {1, -1, 0, 0};
int flag, n, m, k;
bool check(int x, int y) {  //找合法位置，在区域内且不可遇到障碍物
    return x >= 1 && x <= n && y >= 1 && y <= m && mp[x][y] != 'R' &&
           mp[x][y] != 'X';
}
void dfs(int cnt) {
    if (cnt >= k) return;
    if (flag) return;
    for (int i = 1; i <= n; i++)  //这样搜索就不用管理坐标了
        for (int j = 1; j <= m; j++)
            if (mp[i][j] == 'R')               //枚举每一辆车
                for (int k = 0; k < 4; k++) {  //枚举每一个方向
                    int tx = i, ty = j;
                    while (check(tx + dx[k], ty + dy[k]))
                        tx += dx[k], ty += dy[k];     //不断向前
                    if (mp[tx][ty] == 'D') flag = 1;  //如果抵达 设为完成
                    swap(mp[tx][ty], mp[i][j]);       //换过去
                    dfs(cnt + 1);                     //向下搜索
                    swap(mp[tx][ty], mp[i][j]);       //换回来
                }
}
int main() {
    cin >> m >> n >> k;
    for (int i = 1; i <= n; i++) scanf("%s", mp[i] + 1);
    dfs(0);
    puts(flag ? "YES" : "NO");
    return 0;
}

改了一下我比赛的时候写的

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
char s[15][15];
bool finish = 0;
int w, h, ti, a, b;
void turnright(int x, int y) {
    int i;
    for (i = y + 1; i <= w; ++i)
        if (s[x][i] != '.' && s[x][i] != 'D') break;
    if (s[x][i - 1] == 'D') finish = 1;
    a = x, b = i - 1;
}
void turnleft(int x, int y) {
    int i;
    for (i = y - 1; i > 0; --i)
        if (s[x][i] != '.' && s[x][i] != 'D') break;
    if (s[x][i + 1] == 'D') finish = 1;
    a = x, b = i + 1;
}
void turndown(int x, int y) {
    int i;
    for (i = x + 1; i <= h; ++i)
        if (s[i][y] != '.' && s[i][y] != 'D') break;
    if (s[i - 1][y] == 'D') finish = 1;
    a = i - 1, b = y;
}
void turnup(int x, int y) {
    int i;
    for (i = x - 1; i; --i)
        if (s[i][y] != '.' && s[i][y] != 'D') break;
    if (s[i + 1][y] == 'D') finish = 1;
    a = i + 1, b = y;
}
void dfs(int times) {
    if (finish) return;
    if (times > ti) return;
    for (int i = 1; i <= h; ++i)
        for (int j = 1; j <= w; ++j)
            if (s[i][j] == 'R') {
                int xi, yi;
                turnup(i, j), swap(s[i][j], s[a][b]), xi = a, yi = b;
                dfs(times + 1), swap(s[i][j], s[xi][yi]);
                if (finish) return;
                turndown(i, j), swap(s[i][j], s[a][b]), xi = a, yi = b;
                dfs(times + 1), swap(s[i][j], s[xi][yi]);
                if (finish) return;
                turnleft(i, j), swap(s[i][j], s[a][b]), xi = a, yi = b;
                dfs(times + 1), swap(s[i][j], s[xi][yi]);
                if (finish) return;
                turnright(i, j), swap(s[i][j], s[a][b]), xi = a, yi = b;
                dfs(times + 1), swap(s[i][j], s[xi][yi]);
                if (finish) return;
            }
}
int main() {
    scanf("%d%d%d", &w, &h, &ti);
    for (int i = 1; i <= h; ++i) scanf("%s", s[i] + 1);
    dfs(1);
    puts(finish ? "YES" : "NO");
    return 0;
}