完了,一不小心满分了!【满分代码 放心食用】
查看原帖
完了,一不小心满分了!【满分代码 放心食用】
1083725
zhangchenxing1楼主2024/12/7 10:57
#include <bits/stdc++.h>
const int mo = 590027;
using namespace std;

int n, m, mapx[20][20], endx, endy;
long long all_ans, dp[2][600000];

int bits[28];

int state[2][600000], tots[2];
int pre = 1, cnt;

struct hash_table
{
    int pre, to;
}idx[600000];
int ptr[600000], at;

inline void init_bits()
{
    for (int i = 1;i <= 25;i++)
        bits[i] = (i << 1);
}

inline void hah(int sta, long long val)
{
    int key = sta % mo;
    for (int prex = ptr[key];prex;prex = idx[prex].pre)
    {
        if (state[cnt][idx[prex].to] == sta)
        {
            dp[cnt][idx[prex].to] += val;
            return;
        }
    }
    tots[cnt]++;
    state[cnt][tots[cnt]] = sta;
    dp[cnt][tots[cnt]] = val;

    idx[++at].pre = ptr[key];
    idx[at].to = tots[cnt];
    ptr[key] = at;
}

inline void DP()
{
    tots[cnt] = 1;
    dp[cnt][1] = 1;
    state[cnt][1] = 0;

    for (int i = 1;i <= n;i++)
    {
        for (int j = 1;j <= tots[cnt];j++) state[cnt][j] <<= 2;//!!!

        for (int j = 1;j <= m;j++)
        {
            at = 0;
            memset(ptr, 0, sizeof ptr);//clear hash_table
            swap(pre, cnt);//rolling
            tots[cnt] = 0;//clear state counter

            register int nowsta, is_d, is_r;
            register long long nowans;
            for (int k = 1;k <= tots[pre];k++)
            {
                nowsta = state[pre][k], nowans = dp[pre][k];//get previous state&answer
                is_d = (nowsta >> bits[j]) % 4, is_r = (nowsta >> bits[j - 1]) %4 ;//get current plugs

                if (!mapx[i][j])//case 0
                {
                    if ((!is_d) && (!is_r)) hah(nowsta, nowans);
                }

                else if ((!is_d) && (!is_r))//case 1
                {
                    if (mapx[i + 1][j] && mapx[i][j + 1])
                        hah(nowsta + (1 << bits[j - 1]) + 2 * (1 << bits[j]), nowans);
                }

                else if ((!is_d) && is_r)//case 2
                {
                    if (mapx[i + 1][j]) hah(nowsta, nowans);//go down
                    if (mapx[i][j + 1]) hah(nowsta - is_r * (1 << bits[j - 1]) + is_r * (1 << bits[j]), nowans);//go right
                }

                else if (is_d && (!is_r))//case 3
                {
                    if (mapx[i][j + 1]) hah(nowsta, nowans);//go right
                    if (mapx[i + 1][j]) hah(nowsta - is_d * (1 << bits[j]) + is_d * (1 << bits[j - 1]), nowans);//go down
                }

                else if (is_d == 1 && is_r == 1)//case 4
                {
                    register int count = 1;
                    for (int l = j + 1;l <= m;l++)
                    {
                        if ((nowsta >> bits[l]) % 4 == 1) count++;
                        else if ((nowsta >> bits[l]) % 4 == 2) count--;
                        if (!count)
                        {
                            hah(nowsta - (1 << bits[l]) - (1 << bits[j]) - (1 << bits[j - 1]), nowans);
                            break;
                        }
                    }
                }

                else if (is_d == 2 && is_r == 2)//case 5
                {
                    register int count = 1;
                    for (int l = j - 2;l >= 0;l--)
                    {
                        if ((nowsta >> bits[l]) % 4 == 1) count--;
                        else if ((nowsta >> bits[l]) % 4 == 2) count++;
                        if (!count)
                        {
                            hah(nowsta - 2 * (1 << bits[j]) - 2 * (1 << bits[j - 1]) + (1 << bits[l]), nowans);
                            break;
                        }
                    }
                }

                else if (is_d == 1 && is_r == 2)//case 6
                    hah(nowsta - 2 * (1 << bits[j - 1]) - (1 << bits[j]), nowans);

                else if (is_r == 1 && is_d == 2)//case 7
                    if (i == endx && j == endy) all_ans += (long long)nowans;
            }
        }
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1;i <= n;i++)
    {
        for(int j = 1;j <= m;j++)
        {
            char t;
            scanf(" %c", &t);
            if(t == '.')
            {
                mapx[i][j] = 1;
                endx = i;
                endy = j;
            }
        }
    }
    init_bits();
    DP();
    printf("%lld\n", all_ans);
    return 0;
}
2024/12/7 10:57
加载中...