题解：B3983 [信息与未来 2024] AI 机器人

silverleo · 2024-06-29 10:27:30 · 题解

更新下代码，原来代码有点问题没有实现最优复杂度。

先看最简单的情况，一个不含 * 的操作序列路线是固定的并且最后停留的位置唯一，直接按步移动就可以。
然后考虑 (S)* 的情况，可以把每次循环可能停留的位置叠加起来，循环叠加直至位置不再变化为止。用一个 bitset 表示矩阵，例如 (R)* 的停留位置如下：
```
1111111  
0000000  
0000000   
```
后续移动就在之前矩阵基础上移动得到，比如 (R)*D 得到的矩阵为：
```
1111111  
1111111    
0000000   
```
障碍物用另一个矩阵表示， 1 表示空格，0 表示障碍物。为处理方便在每行最后增加一列障碍物，然后每次移动之后的位置有两个来源：
1. 原位置移位之后与空格的交集
2. 原位置与障碍物反向移位后的交集（即被障碍物挡住停留在原地的情况）

用位运算来处理很方便，将两种情况合并就是移动后的结果了。

以样例 3 数据为例，空格矩阵为：

11111110  
10000010    
11111110

起点 (1,1) 经过 (R)* 移动之后得到的位置：

11111110  
00000000    
00000000

再经过 (D)* 移动之后得到的位置：

11111110  
10000010    
10000010

把所有移动过程中经过的点记录下来就是最终答案。

直接提交会超时，要加上记忆化搜索，只需要记录关键指令位 ( 的结果。直接记忆化只能过部分数据，因为整个矩阵的状态数是 2^{n \times m} 级别，显然过大。再观察发现其中每个点可以独立计算互不干扰，因此可以将矩阵拆成点之后再对每个点分别记忆化，最后将所有点的结果合并就是完整的结果了，这样每一步最多只需要保存 {n \times m} 个结果。

复杂度

(S)* 复杂度由指令长度、每个关键节点需要计算的点数、* 的最大循环次数决定，其中 * 循环次数不超过 {n \times m}，每一步需计算的点数也是 {n \times m}，每个点的结果 bitset 合并需要 {n \times m \over w} 开销，复杂度 {O({\lvert S \rvert n^3 m^3 \over w})}。

而 (S)k 虽然只需要循环 {k} 次，但是每次必须把所有点都计算一遍（(S)* 循环每次只需要计算新增的点），复杂度 {O({\lvert S \rvert n^3 m^3 k \over w})} 反而更高。

最终复杂度 {O({\lvert S \rvert n^3 m^3 k \over w})}，可以优化到 {O({\lvert S \rvert n^3 m^3 \log k \over w})}。

完结撒花，小学毕业，哦耶！

代码

#include<bits/stdc++.h>
using namespace std;
typedef bitset<128> GRID;
int n,m,to[1000];
string path;
GRID blank,vis(1),flag(1); 
unordered_map<int,GRID> mp[1000];

GRID move(GRID& g,char ch){
    GRID res;
    if(ch=='U')res=(g>>(m+1)&blank)|(g&~(blank<<(m+1)));//空格位取反即障碍物，行尾加了一列障碍物所以上下移动需要移m+1位 
    else if(ch=='D')res=(g<<(m+1)&blank)|(g&~(blank>>(m+1)));
    else if(ch=='L')res=(g>>1&blank)|(g&~(blank<<1));
    else if(ch=='R')res=(g<<1&blank)|(g&~(blank>>1));
    vis|=res;//移动时记录结果
    return res;
}

GRID solve(int& ind,int p);

GRID solve2(int& ind,GRID g){//将矩阵拆解为每个点来搜索 
    GRID res;
    int start=ind;
    for(int i=0;i<n*(m+1);i++)
        if(g[i]){
            ind=start;
            res|=solve(ind,i);
        }   
    return res;
}

GRID solve(int& ind,int p){//点p从指令位ind执行到')'或结尾得到的结果 
    int t=ind;
    if(mp[t].find(p)!=mp[t].end()){//记忆化搜索
        ind=to[t];
        return mp[t][p];
    }       
    GRID res=flag<<p;       
    while(ind<path.size()){
        char ch=path[ind++];
        if(ch=='('){//遇到左括号进入递归
            int start=ind;
            GRID last=res;
            res=solve2(ind,last);                   
            if(path[ind]=='*'){
                res|=last;//原位置与移动后的位置叠加作为结果，直到结果和原位置重合为止
                GRID diff=res^last;//每次循环只需要搜索新增的点就可以，避免重复搜索 
                while(diff.any()){
                    last=res;
                    ind=start;
                    res=solve2(ind,diff)|last;
                    diff=res^last;
                }
            }else{
                for(int i=0;i<path[ind]-'1';i++){
                    last=res;
                    ind=start;
                    res=solve2(ind,last);
                }
            }
            ind++;
        }else if(ch==')')break;//遇到右括号退出递归
        else res=move(res,ch);
    }   
    to[t]=ind;
    return mp[t][p]=res;
}

int main(){
    cin>>n>>m;
    string s;
    for(int i=0,p=0;i<n;i++,p++){ 
        cin>>s;
        for(int j=0;j<m;j++,p++){
            if(s[j]=='.')blank[p]=1;
        }               
    }
    cin>>path;
    int t=0;
    solve2(t,vis);
    for(int i=0,p=0;i<n;i++,p++){
        for(int j=0;j<m;j++,p++){
            if(!blank[p])cout<<'#';
            else if(vis[p])cout<<'+';
            else cout<<'.';
        }
        cout<<endl;
    }
}