力扣杯春赛 - 个人赛 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 <= 10001 <= 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 <= 10000 <= 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 <= 100forceField[i].length == 30 <= forceField[i][0], forceField[i][1] <= 10^91 <= 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 <= 200maze[i][j] 仅蕴含 "."、"#"、"S"、"T"

问题剖析

不难发现

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

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

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

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

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

工夫复杂度：O( n2log(n) )

空间复杂度：O( n2 )

代码实现

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.lengthm == chessboard[i].length1 <= n*m <= 30chessboard 中仅蕴含 "."、"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][c] == '?') {        // ?置为空：以后行和全局列的状态不扭转        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][c] == 'B' && !check(0) ||            g[r][c] == '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][c] == '?') {        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][c] == 'B' && !check(0) ||            g[r][c] == '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);;}