关于算法:算法竞赛力扣杯春赛个人赛-LCCUP23复盘

力扣杯春赛 – 个人赛 LCCUP’23

LCP 72. 补给马车

关键词：模仿

题目起源：LCP 72. 补给马车 – 力扣（Leetcode）

题目形容

 T 模仿

远征队行将开启未知的冒险之旅，不过在此之前，将对补给车队进行最初的查看。supplies[i] 示意编号为 i 的补给马车装载的物资数量。思考到车队过长容易被野兽偷袭，他们决定将车队的长度变为原来的一半（向下取整），打算为：

• 找出车队中 物资之和最小 两辆 相邻 马车，将它们车辆的物资整合为一辆。若存在多组物资之和雷同的马车，则取编号最小的两辆马车进行整合；
• 反复上述操作直到车队长度符合要求。

请返回车队长度符合要求后，物资的散布状况。

输出：supplies = [7,3,6,1,8]
输入：[10,15]

输出：supplies = [1,3,1,5]
输入：[5,5]

数据范畴
2 <= supplies.length <= 1000
1 <= supplies[i] <= 1000

问题剖析

察看数据范畴，O(n^2)的工夫复杂度是能够承受的，本题采纳模仿即可。具体做法如下：

合并次数 m =n-(n>>1)，对于每次合并

1. 扫描一遍数组，找到和最小的相邻两个元素，设为 i，j
2. 执行合并操作，即 a[i]+=a[j]；将 j 标记为不存在，即 a[j]=0

最初，将残余元素取出返回即可。

工夫复杂度：O(n^2)

空间复杂度：O(n)

vector<int> supplyWagon(vector<int> &supplies) {int n = supplies.size(), m = n - (n >> 1);
    // m 次合并
    while (m--) {
        // 找到和最小的相邻两个元素
        int sum = INT_MAX, mi, mj;
        for (int i = 0, j; i < n; i = j) {
            // 相邻两个元素 i 和 j
            while (i < n && supplies[i] == 0)i++;
            j = i + 1;
            while (j < n && supplies[j] == 0)j++;
            // 比拟和
            if (j < n && supplies[i] + supplies[j] < sum) {sum = supplies[i] + supplies[j], mi = i, mj = j;
            }
        }
        // 合并
        supplies[mi] += supplies[mj], supplies[mj] = 0;
    }
    // 将残余元素取出
    vector<int> ans;
    for (const auto &e: supplies) {if (e != 0)ans.push_back(e);
    }
    return ans;
}

LCP 73. 探险营地

关键词：字典树、STL

题目起源：LCP 73. 探险营地 – 力扣（Leetcode）

问题形容

 T 字典树
 TSTL

探险家小扣的口头轨迹，都将保留在记录仪中。expeditions[i] 示意小扣第 i 次探险记录，用一个字符串数组示意。其中的每个「营地」由大小写字母组成，通过子串 -> 连贯。

例：”Leet->code->Campsite”，示意到访了 “Leet”、”code”、”Campsite” 三个营地。

expeditions[0] 蕴含了初始小扣已知的所有营地；对于之后的第 i 次探险 (即 expeditions[i] 且 i > 0)，如果记录中蕴含了之前均没呈现的营地，则示意小扣 新发现 的营地。

请你找出小扣发现新营地最多且索引最小的那次探险，并返回对应的记录索引。如果所有探险记录都没有发现新的营地，返回 -1

留神：

• 大小写不同的营地视为不同的营地；
• 营地的名称长度均大于 0。

输出：expeditions = ["leet->code","leet->code->Campsite->Leet","leet->code->leet->courier"]
输入：1

输出：expeditions = ["Alice->Dex","","Dex"]
输入：-1

输出：expeditions = ["","Gryffindor->Slytherin->Gryffindor","Hogwarts->Hufflepuff->Ravenclaw"]
输入：2

数据范畴
1 <= expeditions.length <= 1000
0 <= expeditions[i].length <= 1000
探险记录中只蕴含大小写字母和子串 "->"

问题剖析

本题的外围问题就是：对于统计 s[i]中有多少个“子串”没在 s[0..1]中呈现过。对于“查找字符串是否呈现过”这类问题，很天然就想到字典树。若不采纳字典树，可间接借助 STL 中的 set。

字典树—数组

若采纳字典树，对于本题而言，查问和插入可同时进行。

这里存在一个问题：N 该指定多大呢？一般来说，最多有多少个结点，N 就指定为多大，依据题目给出的数据范畴，N 应该为 1e6（理论应比 1e6 稍大，防止越界），然而，这显然会超内存。通过测试，N 大略能够到 4e5，不会超内存且能通过本题，能够说，十分幸运。

const int N = 4e5 + 5;
int son[N][52], n;
bool fg[N];

/**
 * 查看字符串 s 是否存在，不存在则将其插入字典树中
 */
bool check(const string &s) {
    int p = 0, u;
    for (auto &c: s) {
        u = c < 'a' ? c - 'A' : c - 'a' + 26;
        if (!son[p][u])son[p][u] = ++n;
        p = son[p][u];
    }
    if (fg[p])return true;  // 已存在
    fg[p] = true;           // 标记已存在
    return false;           // 原先不存在
}

写好字典树相干的代码，前面只须要遍历统计就能够了。

/**
 * 查看 s 中有多少子串还不存在
 */
int count(const string &s) {
    int cnt = 0;
    if (!s.empty()) {
        int i, j;
        for (i = 0, j = s.find('-'); j != string::npos; i = j + 2, j = s.find('-', i)) {if (!check(s.substr(i, j - i))) cnt++;
        }
        if (!check(s.substr(i)))cnt++;
    }
    return cnt;
}

int adventureCamp(vector<string> &expeditions) {
    // 将初始字符串插入字典树
    count(expeditions[0]);
    // 找到发现新营地最多的那次探险
    int len = expeditions.size(), maxCam = 0, idx = -1, curCam;
    for (int i = 1; i < len; i++) {curCam = count(expeditions[i]);
        if (curCam > maxCam)maxCam = curCam, idx = i;
    }
    return idx;
}

工夫 604 ms 内存 120.4 MB

字典树—指针

后面采纳数组的形式，须要预先指定数组大小，所以，咱们能够采纳指针，动态分配结点。

struct Node {Node *child[52]{nullptr};
    bool vis{false};
} *root;

/**
 * 查看字符串 s 是否存在，不存在则将其插入字典树中
 */
bool check(const string &s) {
    auto p = root;
    int u;
    for (const char &c: s) {
        // 映射到 0~52
        u = c < 'a' ? c - 'A' : c - 'a' + 26;
        if (p->child[u] == nullptr) {p->child[u] = new Node();}
        p = p->child[u];
    }
    if (p->vis)return true; // 已存在
    p->vis = true;          // 标记已存在
    return false;           // s 原先不存在
}

须要留神的是，采纳指针的形式所占用的内存会比采纳数组的形式多不少。

int count(const string &s){// 同上}

int adventureCamp(vector<string> &expeditions) {// 同上}

工夫 620 ms 内存 529.3 MB

STL—set 汇合

本题的外围操作就是判断一个字符串是否存在，因而，能够间接利用 set 来寄存已存在的的字符串

/**
 * 查看 s 中有多少子串还不存在
 */
int count(const string &s) {
    int cnt = 0;
    if (!s.empty()) {
        int i, j;
        string ts;
        for (i = 0, j = s.find('-'); j != string::npos; i = j + 2, j = s.find('-', i)) {ts = s.substr(i, j - i);
            if (st.find(ts) == st.end()) {st.insert(ts), cnt++;
            }
        }
        ts = s.substr(i);
        if (st.find(ts) == st.end()) {st.insert(ts), cnt++;
        }
    }
    return cnt;
}

尽管这能够算作暴力做法，但无论是在工夫还是在空间上，都远优于字典树。

int adventureCamp(vector<string> &expeditions) {// 同上}

工夫 316 ms 内存 53.2 MB

LCP 74. 最强祝愿力场

关键词：差分、前缀和、线段树、扫描线

题目起源：LCP 74. 最强祝愿力场 – 力扣（Leetcode）

题目形容

 T 差分
 T 前缀和
 T 线段树
 T 扫描线

小扣在摸索丛林的过程中，无意间发现了传说中“落寞的黄金之都”。而在这片修建废墟的地带中，小扣应用探测仪监测到了存在某种带有「祝愿」成果的力场。通过一直的勘测记录，小扣将所有力场的散布都记录了下来。forceField[i] = [x,y,side] 示意第 i 片力场将笼罩以坐标 (x,y) 为核心，边长为 side 的正方形区域。

若任意一点的 力场强度 等于笼罩该点的力场数量，申请出在这片地带中 力场强度 最强处的 力场强度。

留神：力场范畴的边缘同样被力场笼罩。

输出：forceField = [[0,0,1],[1,0,1]]
输入：2

<img src=”img/LCP74_01.png” style=”zoom: 33%;” />

输出：forceField = [[4,4,6],[7,5,3],[1,6,2],[5,6,3]]
输入：3

<img src=”img/LCP74_02.png” style=”zoom:33%;” />

数据范畴
1 <= forceField.length <= 100
forceField[i].length == 3
0 <= forceField[i][0], forceField[i][1] <= 10^9
1 <= forceField[i][2] <= 10^9

问题剖析

粗略一看，本题须要用扫描线来做，然而，察看数据范畴发现，正方形的数量较少，正方形可能很大，对于这种“量少值大”的状况，极有可能应用到离散化，而离散化通常又和前缀和 / 差分一起呈现，于是思考，是否应用前缀和和差分来解决此题。

题目要求的是被笼罩次数最多的点的被笼罩次数，对于每个正方形而言，其能够使得范畴内的所有点的被笼罩次数 +1，奢侈想法就是，就出所有点被笼罩的次数，求最大值，便是本题的答案。而将一个矩形范畴内的元素对立进行 + 1 操作，这正是二维差分所善于的。

然而，本题的坐标值十分的大，因而须要将坐标离散化，且是有序离散化。那离散化会不会影响答案呢？

证实：离散化不影响答案

设点 p 为力场强度最强的点，则必然存在这样一个最小矩形，其蕴含点 p，且矩形内所有的点的力场强度均相等。留神，这样的矩形不肯定是题目所给的矩形，而是由题目所给矩形的边围成的矩形，且可能是一条线，且 p 可能在矩形边上。

于是，必然存在一点 q，其力场强度是最强的，且位于某个题目所给矩形的边上。

设 t 是题目所给的任意矩形的任意边上的任意一点，进行有序离散化后：

• 本来在 yt 下边的横线仍在 yt 下边
• 原来在 yt 上边的横线仍在 yt 上边
• 原来在 xt 右边的竖线仍在 xt 右边
• 原来在 xt 左边的竖线仍在 xt 左边

也即，点 t 被笼罩的次数并没有变，而对于其余非边上点，进行离散化后已全副被剔除，故最终的答案不变，证毕。

工夫复杂度：O(n^2)

空间复杂度：O(n^2)

代码实现

留神 int 溢出问题

typedef long long ll;

const int N = 2e2 + 5;
ll x[N], y[N];
int g[N][N], nx, ny;

/**
 * 离散化（从 1 开始）*/
int find(ll u, bool isX) {
    return isX ?
           lower_bound(x, x + nx, u) - x + 1
               :
           lower_bound(y, y + ny, u) - y + 1;
}

int fieldOfGreatestBlessing(vector<vector<int>> &forceField) {int n = forceField.size();

    // 记录所有呈现的 x 坐标、y 坐标
    for (int i = 0; i < n; i++) {auto &v = forceField[i];
        v[0] <<= 1, v[1] <<= 1;
        x[i << 1] = v[0] - v[2], x[i << 1 | 1] = (ll) v[0] + v[2];
        y[i << 1] = v[1] - v[2], y[i << 1 | 1] = (ll) v[1] + v[2];
    }

    // 排序去重
    n <<= 1;
    sort(x, x + n), sort(y, y + n);
    nx = unique(x, x + n) - x, ny = unique(y, y + n) - y;

    // 二维差分
    int x1, y1, x2, y2;
    for (auto &v: forceField) {
        // 离散化
        x1 = find(v[0] - v[2], true);
        x2 = find((ll) v[0] + v[2], true);
        y1 = find(v[1] - v[2], false);
        y2 = find((ll) v[1] + v[2], false);
        // 差分
        g[x1][y1]++, g[x2 + 1][y2 + 1]++;
        g[x1][y2 + 1]--, g[x2 + 1][y1]--;
    }

    // 找到被笼罩最多的点
    int maxCover = 0;
    for (int i = 1; i <= nx; i++) {for (int j = 1; j <= ny; j++) {g[i][j] += g[i - 1][j] + g[i][j - 1] - g[i - 1][j - 1];
            maxCover = max(g[i][j], maxCover);
        }
    }

    return maxCover;
}

LCP 75. 传送卷轴

关键词：单源最短路、深度优先、广度优先

题目起源：LCP 75. 传送卷轴 – 力扣（Leetcode）

题目形容

 T 单源最短路
 T 深度优先
 T 广度优先

随着一直的深刻，小扣来到了守护者之森寻找的魔法水晶。首先，他必须先通过守护者的考验。

考验的区域是一个正方形的迷宫，maze[i][j] 示意在迷宫 i 行 j 列的地形：

• 若为 .，示意能够达到的空地；
• 若为 #，示意不可达到的墙壁；
• 若为 S，示意小扣的初始地位；
• 若为 T，示意魔法水晶的地位。

小扣每次能够向 上、下、左、右 相邻的地位挪动一格。而守护者领有一份「传送魔法卷轴」，应用规定如下：

• 魔法须要在小扣位于 空地 时能力开释，动员后卷轴隐没；；
• 动员后，小扣会被传送到程度或者竖直的镜像地位，且指标地位不得为墙壁；

在应用卷轴后，小扣将被「附加负面成果」，因而小扣须要尽可能缩短传送后达到魔法水晶的间隔。而守护者的指标是阻止小扣达到魔法水晶的地位；如果无奈阻止，则尽可能 减少 小扣传送后达到魔法水晶的间隔。假如小扣和守护者都按最优策略行事，返回小扣须要在「附加负面成果」的状况下 起码 挪动多少次能力达到魔法水晶。如果无奈达到，返回 -1。

留神：

• 守护者能够不应用卷轴；
• 传送后的镜像地位可能与原地位雷同。

输出：maze = [".....","##S..","...#.","T.#..","###.."]
输入：7
解释：守护者开释魔法的两个最佳的地位为 [2,0] 或 [3,1]：若小扣通过 [2,0]，守护者在该地位开释魔法，小扣被传送至 [2,4] 处且加上负面成果，此时小扣还须要挪动 7 次能力达到魔法水晶；若小扣通过 [3,1]，守护者在该地位开释魔法，小扣被传送至 [3,3] 处且加上负面成果，此时小扣还须要挪动 9 次能力达到魔法水晶；因而小扣负面成果下起码须要挪动 7 次能力达到魔法水晶。

输出：maze = [".#..","..##",".#S.",".#.T"]
输入：-1
解释：若小扣向下挪动至 [3,2]，守护者使其传送至 [0,2]，小扣将无奈达到魔法水晶；若小扣向右挪动至 [2,3]，守护者使其传送至 [2,0]，小扣将无奈达到魔法水晶；

输出：maze = ["S###.","..###","#..##","##..#","###.T"]
输入：5
解释：守护者须要小扣在空地能力开释，因而初始无奈将其从 [0,0] 传送至 [0,4]; 当小扣挪动至 [2,1] 时，开释卷轴将其传送至程度方向的镜像地位 [2,1]（为原地位）而后小扣须要挪动 5 次达到魔法水晶

数据范畴
4 <= maze.length == maze[i].length <= 200
maze[i][j] 仅蕴含 "."、"#"、"S"、"T"

问题剖析

不难发现

• 若在「附加负面成果」的状况下挪动不超过 k 步能达到魔法水晶，在不超过 k + 1 步也能达到起点
• 若在「附加负面成果」的状况下挪动不超过 k 步不能到达魔法水晶，在不超过 k - 1 步也不能到达起点

因而 k 值具备枯燥性，可二分求解满足条件的 k 的最小值。

check(k)的工作就是，判断是否在「附加负面成果」的状况下挪动不超过 k 步达到魔法水晶，“是否存在通路”这类问题可采纳 dfs 来做。

施加魔法后，须要直到新地位达到起点起码须要多少步，因而须要预处理出起点到每个地位的最短距离，“求最短通路”可采纳 bfs 来做。

综上：bfs 预处理出起点到每个点的最短距离，整体框架是二分，通过 dfs 判断是否存在通路。

工夫复杂度：O(n²log(n) )

空间复杂度：O(n² )

代码实现

typedef pair<int, int> P;
const int N = 2e2 + 5, INF = 0x3f3f3f3f;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};
P s, t;
int n, d[N][N];
bool vis[N][N];

/**
 * 初始化每个点到起点的最短距离
 */
void initDis(vector<string> &maze) {memset(d, 0x3f, sizeof d);
    queue<P> q;
    int sep = d[t.first][t.second] = 0, u, v, lay;
    q.push(t);
    while (!q.empty()) {
        // 每遍历一层，与起点的间隔便 +1
        sep++, lay = q.size();
        // 以后层所有结点与起点的间隔均为 sep
        while (lay--) {
            // 取出队头结点
            P tp = q.front();
            // 拓展结点
            for (int i = 0; i < 4; i++) {u = tp.first + dx[i], v = tp.second + dy[i];
                if (u < 0 || u >= n || v < 0 || v >= n ||
                    maze[u][v] == '#' || d[u][v] < INF
                        )
                    continue;
                if (u >= n || v >= n) {cout << "!!!";}
                d[u][v] = sep;
                q.push({u, v});
            }
            // 后面应用援用，所以要等到应用完后出队
            q.pop();}
    }
}

/**
 * 查看是否使得附加负面成果的步数不超过 sep 步达到起点
 */
bool dfs(int sep, int x, int y, vector<string> &maze) {

    // 越界或障碍物或已拜访
    if (x < 0 || x >= n || y < 0 || y >= n ||
        maze[x][y] == '#' || vis[x][y]
            )
        return false;

    // 达到起点
    if (x == t.first && y == t.second)return true;

    if (x >= n || y >= n) {cout << "!!!";}

    // 标记已拜访
    vis[x][y] = true;

    // 施展魔法
    // 体现守护者的最优策略
    if (maze[x][y] == '.') {
        // 如果能传送到一个应用 sep 不能到达起点的点，阐明以后路在限度为 sep 的状况下不可
        if (maze[x][n - y - 1] != '#' && d[x][n - y - 1] > sep)return false;
        if (maze[n - x - 1][y] != '#' && d[n - x - 1][y] > sep)return false;
    }


    // 只有存在一条路在施加负面成果的状况下可在 sep 步内达到起点，阐明 sep 步肯定可达到起点
    // 体现小扣的最优策略
    for (int i = 0; i < 4; i++)
        if (dfs(sep, x + dx[i], y + dy[i], maze))return true;

    return false;
}

int challengeOfTheKeeper(vector<string> &maze) {n = maze.size();
    // 找到终点和起点
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (maze[i][j] == 'S')s = {i, j};
            else if (maze[i][j] == 'T')t = {i, j};

    // 初始化每个点到起点的最短距离
    initDis(maze);

    // 终点无奈达到起点
    if (d[s.first][s.second] >= INF)return -1;

    // 二分答案
    int l = 0, r = n * n, mid;
    while (l < r) {mid = (l + r) >> 1;
        memset(vis, 0, sizeof vis);
        if (dfs(mid, s.first, s.second, maze))r = mid;
        else l = mid + 1;
    }

    return l == n * n ? -1 : l;
}

LCP 76. 魔法棋盘

关键词：深度优先、状态压缩

在大小为 n * m 的棋盘中，有两种不同的棋子：彩色，红色。当两颗色彩不同的棋子同时满足以下两种状况时，将会产生魔法共鸣：

• 两颗异色棋子在同一行或者同一列
• 两颗异色棋子之间恰好只有一颗棋子

注：异色棋子之间能够有空位

因为棋盘上被施加了魔法禁制，棋盘上的局部格子变成问号。chessboard[i][j] 示意棋盘第 i 行 j 列的状态：

• 若为 .，示意以后格子确定为空
• 若为 B，示意以后格子确定为 黑棋
• 若为 R，示意以后格子确定为 红棋
• 若为 ?，示意以后格子待定

当初，探险家小扣的工作是确定所有问号地位的状态（留空 / 放黑棋 / 放红棋），使最终的棋盘上，任意两颗棋子间都 无奈 产生共鸣。请返回能够满足上述条件的搁置计划数量。

输出：n = 3, m = 3, chessboard = ["..R","..B","?R?"]
输入：5

输出：n = 3, m = 3, chessboard = ["?R?","B?B","?R?"]
输入：105

数据范畴
n == chessboard.length
m == chessboard[i].length
1 <= n*m <= 30
chessboard 中仅蕴含 "."、"B"、"R"、"?"

问题剖析

思考到数据范畴较小，因而，可采纳深搜来枚举每种计划。

对于地位(i,j)

• 若为?，则将将其置为空 / 黑棋 / 红棋，搁置是否非法，须要参考目前棋盘的状态
• 若为.，则间接往后深搜即可，因为空位不影响后果。
• 若为 B 或 R，则须要判断目前的状态是否非法，若非法则往后深搜

从左往右从上到下的程序（先列后行）搜寻，每当搜完最初一个地位，便失去一种计划。

如何寄存以后的状态呢？因为状态较多，一来要有助于疾速判断是否非法，二来要节约空间，天然就想到状态压缩。

对于每一行 / 每一列，其非法的状态不外乎以下 7 类：

• 空：即全为“.”
• 仅一个 B：如，“…B”，“..B….”
• 仅一个 R：如，“.R….”，“R.”
• 多个 B：如，“.B..B”，“…BB”
• 多个 R：如，“RR..”，“R…RR..R”
• BR 交替且结尾为 B：如，“BRB…”，“..RB..”
• BR 交替且结尾为 R：如，“RB…R..BR”，“…R..B..R..”

故可用 3 位二进制来示意所有非法的单行 / 列状态。

对于?，因为将其置空不影响状态，故只需思考置黑棋和置红棋的状况，于是，能够预处理出一张状态转换表 T，借助表 T，可疾速判断是否非法。

因为地位 (i,j) 能放什么，是否非法，仅与所在行和所在列无关，且按从左往右从上到下，故须要记录以后行和所有列的信息。每列用 3 位二进制示意，且能够保障列数不超过 5，故可用 15 位二进制示意所有列的状态，也即一个整数即可。

代码实现

不带记忆化：能过大部分测试用例

typedef pair<int, int> P;

const int N = 35;
char g[N][N];
int rn, cm;
long long ans;

// 状态转换表
int T[7][2] = {
        // + B 后的状态   + R 后的状态
        {1,  2},     // 空
        {3,  6},      // 一个 B
        {5,  4},      // 一个 R
        {3,  -1},     // 多个 B
        {-1, 4},     // 多个 R
        {-1, 6},     // BR 交替且以 B 结尾
        {5,  -1}      // BR 交替且以 R 结尾
};

/**
 * 枚举 (i,j) 的所有可能值
 * rs：以后行的状态
 * state：0~2 位寄存第 1 列的状态，3~5 位寄存第 2 列的状态，12~14 位寄存第 5 列的状态
 */
void dfs(int r, int c, int rs, int state) {

    // 最初一行的状态已被枚举完：失去一种计划
    if (r == rn) {
        ans++;
        return;
    }

    // 以后行已枚举完，开始枚举下一行
    if (c == cm) {dfs(r + 1, 0, 0, state);
        return;
    }

    // 寄存下一状态
    P p = {rs, state};

    // 查看在 (r,c) 追加色彩为 C 的棋是否正当，正当则将新的状态保留到 p 中
    auto check = [&](int C) {
        int c3 = c * 3;
        if (T[rs][C] == -1 || T[(state >> c3) & 7][C] == -1)return false;
        p = {T[rs][C], state & ~(7 << c3) | (T[(state >> c3) & 7][C] << c3)};
        return true;
    };

    // 问号
    if (g[r] == '?') {
        // ? 置为空：以后行和全局列的状态不扭转
        dfs(r, c + 1, rs, state);
        // ? 置为 B
        if (check(0))dfs(r, c + 1, p.first, p.second);
        // ? 置为 R
        if (check(1))dfs(r, c + 1, p.first, p.second);
        return;
    }
        // 黑棋或红棋：判断是否与曾经填充的抵触
    else if (g[r] == 'B' && !check(0) ||
            g[r] == 'R' && !check(1)
            )
        return;
    // 空位 ||(黑棋或红棋正当)
    // 若为空位，则 p 就为初始状态
    // 若为黑棋或红棋正当，则 p 在 check 时就已被批改为新的状态
    dfs(r, c + 1, p.first, p.second);
}

long long getSchemeCount(int n, int m, vector<string> &chessboard) {
    // 确保 m≤n
    if (n >= m) {
        rn = n, cm = m;
        for (int i = 0; i < n; i++)
            sscanf(chessboard[i].c_str(), "%s", g[i]);
    } else {
        rn = m, cm = n;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                g[j][i] = chessboard[i][j];
    }
    // 深搜
    dfs(0, 0, 0, 0);
    return ans;
}

带记忆化：能 AC

typedef long long ll;
typedef pair<int, int> P;

const int N = 32, M = 28087;
char g[N][N];
int rn, cm;
ll f[N][8][M];

// 状态转换表
int T[7][2] = {
        // + B 后的状态   + R 后的状态
        {1,  2},     // 空
        {3,  6},      // 一个 B
        {5,  4},      // 一个 R
        {3,  -1},     // 多个 B
        {-1, 4},     // 多个 R
        {-1, 6},     // BR 交替且以 B 结尾
        {5,  -1}      // BR 交替且以 R 结尾
};

/**
 * 枚举 (i,j) 的所有可能值
 * rs：以后行的状态
 * state：0~2 位寄存第 1 列的状态，3~5 位寄存第 2 列的状态，12~14 位寄存第 5 列的状态
 * 返回目前状态为 rs 和 state 的状况下，从 (i,j) 开始枚举，失去的计划数
 */
ll dfs(int r, int c, int rs, int state) {

    // 最初一行的状态已被枚举完：失去一种计划
    if (r == rn) return 1;

    // 以后行已枚举完，开始枚举下一行
    if (c == cm)
        return dfs(r + 1, 0, 0, state);

    // 记忆化
    ll &v = f[r * cm + c][rs][state];
    if (v != -1)return v;

    // 寄存下一状态
    P p = {rs, state};

    // 查看在 (r,c) 追加色彩为 C 的棋是否正当，正当则将新的状态保留到 p 中
    auto check = [&](int C) {
        int c3 = c * 3;
        if (T[rs][C] == -1 || T[(state >> c3) & 7][C] == -1)return false;
        p = {T[rs][C], state & ~(7 << c3) | (T[(state >> c3) & 7][C] << c3)};
        return true;
    };

    // 问号
    if (g[r] == '?') {
        v = 0;
        // ? 置为空：以后行和全局列的状态不扭转
        v += dfs(r, c + 1, rs, state);
        // ? 置为 B
        if (check(0))v += dfs(r, c + 1, p.first, p.second);
        // ? 置为 R
        if (check(1))v += dfs(r, c + 1, p.first, p.second);
        return v;
    }
        // 黑棋或红棋：判断是否与曾经填充的抵触
    else if (g[r] == 'B' && !check(0) ||
            g[r] == 'R' && !check(1)
            )
        return v=0;
    // 空位 ||(黑棋或红棋正当)
    // 若为空位，则 p 就为初始状态
    // 若为黑棋或红棋正当，则 p 在 check 时就已被批改为新的状态
    return v = dfs(r, c + 1, p.first, p.second);
}

long long getSchemeCount(int n, int m, vector<string> &chessboard) {
    // 确保 m≤n
    if (n >= m) {
        rn = n, cm = m;
        for (int i = 0; i < n; i++)
            sscanf(chessboard[i].c_str(), "%s", g[i]);
    } else {
        rn = m, cm = n;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                g[j][i] = chessboard[i][j];
    }
    // 深搜
    memset(f, -1, sizeof f);
    return dfs(0, 0, 0, 0);;
}