题解：B4299 [蓝桥杯青少年组国赛 2022] 路线

· · 题解

B4299 [蓝桥杯青少年组国赛 2022] 路线

入门题库的题一定要能入门啊。

前置知识

建议先通过 P5056 后再来挑战本题。

:::info[如果你已经通过 P5056] 建议你自主思考，解决本题。

本题的答案仅仅是哈密顿回路数量的二倍。 :::

题意&解法

很明显，本题与 P5056 的最大区别是没有障碍，不需要考虑障碍。

以防你没做过 P10975 Mondriaan's Dream / 蒙德里安的梦想，顺便补一下 P5056 题解关于轮廓线的介绍：

（图中黄色部分为已经计算过的部分，红色即为轮廓线，省略路径数）

轮廓线就是如上图红线，轮廓线 DP 的核心就是维护轮廓线上每个插头（小格子）的状态。

同 P5056，本题也有 3 个状态，我们记：

那么如下图的轮廓线状态我们就可以记为 02121021（从左向右，图中青色部分为未经过部分）。

::::info[关于上图的一个解释] 在遍历到当前轮廓线状态时，我们不知道轮廓线一下的情况，这里画出来只是为了好理解。 ::::

至于状态的转移……同 P5056，这里不再赘述，可见 P5056 题解。

最终答案为 P5056 的二倍。

code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
//十年OI一场空，不开long long见祖宗
int n , m , ex , ey;
char s[15][15];
int flag[15][15];
map<int , LL> dp , pre;
int num[20] , mx;
inline void decode(int x){//解码
    for(int i = 0 ; i <= m ; ++i)
        num[i] = 0;
    int c = 0;
    while(x){
        num[m - c] = x & 3;
        x >>= 2;
        c += 1;
    }
}
int encode(){//编码
    int res = 0;
    for(int i = 0 ; i < mx ; ++i)
        res = (res << 2) + num[i];
    return res;
}
int main(){
    //freopen(".in" , "r" , stdin);
    //freopen(".out" , "w" , stdout);
    scanf("%d%d" , &n , &m);
    for(int i = 0 ; i < n ; ++i)
        scanf("%s" , s[i]);
    ex = n - 1 , ey = m;//最后的不是障碍的位置
    for(int i = 0 ; i < n ; ++i)
        for(int j = 1 ; j <= m ; ++j)
            flag[i][j] = 1;
    mx = m + 1;
    dp[0] = 1;
    for(int i = 0 ; i < n ; ++i){
        for(int j = 0 ; j <= m ; ++j){
            if(i == ex && j == ey){
                printf("%lld\n" , dp[0] * 2);
                return 0;
            }
            swap(pre , dp);
            dp.clear();
            for(auto k : pre){
                LL v = k.second;
                decode(k.first);
                if(j == m){
                    if(num[j] == 0)
                        dp[k.first >> 2] += v;
                    continue;
                }
                int a = num[j] , b = num[j + 1];
                if(flag[i][j + 1] == 0){
                    if(a == 0 && b == 0)
                        dp[k.first] += v;
                    continue;
                }
                if(a == 0 && b == 0){
                    num[j] = 1 , num[j + 1] = 2;
                    dp[encode()] += v;
                }
                if(a == 1 && b == 2 && i == ex && j + 1 == ey){
                    num[j] = 0 , num[j + 1] = 0;
                    dp[encode()] += v;
                }
                if(a == 1 && b == 1){
                    num[j] = num[j + 1] = 0;
                    int f = 0 , c1 = 1;
                    for(int l = j + 2 ; l <= m ; ++l){
                        if(num[l] == 1)
                            c1 += 1;
                        if(num[l] == 2){
                            c1 -= 1;
                            if(c1 == 0){
                                num[l] = 1;
                                f = 1;
                                break;
                            }
                        }
                    }
                    if(f)
                        dp[encode()] += v;
                }
                if(a == 2 && b == 2){
                    num[j] = num[j + 1] = 0;
                    int f = 0 , c2 = 1;
                    for(int l = j - 1 ; l >= 0 ; --l){
                        if(num[l] == 2)
                            c2 += 1;
                        if(num[l] == 1){
                            c2 -= 1;
                            if(c2 == 0){
                                num[l] = 2;
                                f = 1;
                                break;
                            }
                        }
                    }
                    if(f)
                        dp[encode()] += v;
                }
                if(a == 0 && b == 1){
                    dp[k.first] += v;
                    num[j] = 1 , num[j + 1] = 0;
                    dp[encode()] += v;
                }
                if(a == 1 && b == 0){
                    dp[k.first] += v;
                    num[j] = 0 , num[j + 1] = 1;
                    dp[encode()] += v;
                }
                if(a == 0 && b == 2){
                    dp[k.first] += v;
                    num[j] = 2 , num[j + 1] = 0;
                    dp[encode()] += v;
                }
                if(a == 2 && b == 0){
                    dp[k.first] += v;
                    num[j] = 0 , num[j + 1] = 2;
                    dp[encode()] += v;
                }
                if(a == 2 && b == 1){
                    num[j] = 0 , num[j + 1] = 0;
                    dp[encode()] += v;
                }
            }
        }
    }
    return 0;
}