如题,在这道题的提交过程中发现了非常诡异的错误。
首先给出我的 AC 代码:
#include <iostream>
#include <cctype>
#include <string.h>
#define ll long long
using namespace std;
ll read()
{
ll x = 0, f = 1;
char ch = 0;
while (!isdigit(ch))
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (isdigit(ch))
{
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
const ll P = 299987;
ll n, m; // 棋盘的行数和列数
ll ex, ey; // 最后一个非障碍格子的坐标
ll now, last;
ll ans;
ll a[13][13]; // 记录棋盘
ll head[300000];
ll nxt[2 << 24];
ll que[2][2 << 24];
ll val[2][2 << 24];
ll cnt[2];
ll inc[13]; // 2 的幂次方
void init()
{
n = read();
m = read();
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
char ch = getchar();
while (ch != '*' && ch != '.')
ch = getchar();
if (ch != '.')
a[i][j] = 0;
else
{
a[i][j] = 1;
ex = i;
ey = j;
}
}
inc[0] = 1;
for (int i = 1; i <= 13; i++)
inc[i] = inc[i - 1] << 2;
}
void insert(ll bit, ll num)
{
ll u = bit % P + 1;
for (int i = head[u]; i; i = nxt[i])
if (que[now][i] == bit)
{
val[now][i] += num;
return;
}
nxt[++cnt[now]] = head[u];
head[u] = cnt[now];
que[now][cnt[now]] = bit;
val[now][cnt[now]] = num;
}
void solve()
{
cnt[now] = 1;
val[now][1] = 1;
que[now][1] = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= cnt[now]; j++)
que[now][j] <<= 2;
for (int j = 1; j <= m; ++j)
{
memset(head, 0, sizeof(head));
last = now;
now ^= 1;
cnt[now] = 0;
for (int k = 1; k <= cnt[last]; ++k)
{
ll bit = que[last][k], num = val[last][k];
ll b1 = (bit >> ((j - 1) * 2)) % 4, b2 = (bit >> (j * 2)) % 4;
if (!a[i][j])
{
if (!b1 && !b2)
insert(bit, num);
}
else if (!b1 && !b2)
{
if (a[i + 1][j] && a[i][j + 1])
insert(bit + inc[j - 1] + inc[j] * 2, num);
}
else if (!b1 && b2)
{
if (a[i][j + 1])
insert(bit, num);
if (a[i + 1][j])
insert(bit - inc[j] * b2 + inc[j - 1] * b2, num);
}
else if (b1 && !b2)
{
if (a[i + 1][j])
insert(bit, num);
if (a[i][j + 1])
insert(bit - inc[j - 1] * b1 + inc[j] * b1, num);
}
else if (b1 == 1 && b2 == 1)
{
int flag = 1;
for (int l = j + 1; l <= m; ++l)
{
if ((bit >> (l * 2)) % 4 == 1)
flag++;
if ((bit >> (l * 2)) % 4 == 2)
flag--;
if (!flag)
{
insert(bit - inc[j] - inc[j - 1] - inc[l], num);
break;
}
}
}
else if (b1 == 2 && b2 == 2)
{
int flag = 1;
for (int l = j - 2; l >= 0; --l)
{
if ((bit >> (l * 2)) % 4 == 1)
flag--;
if ((bit >> (l * 2)) % 4 == 2)
flag++;
if (!flag)
{
insert(bit - inc[j] * 2 - inc[j - 1] * 2 + inc[l], num);
break;
}
}
}
else if (b1 == 2 && b2 == 1)
insert(bit - inc[j - 1] * 2 - inc[j], num);
else if (i == ex && j == ey)
ans += num;
}
}
}
}
int main()
{
init();
solve();
printf("%lld", ans);
return 0;
}
这里有两个问题:
ll a[13][13];
ll head[300000];
ll nxt[2 << 24];
ll que[2][2 << 24];
ll val[2][2 << 24];
ll cnt[2];
ll inc[13];
如果我将 ll inc[13] 往前放,即修改成
ll a[13][13];
ll inc[13];
ll head[300000];
ll nxt[2 << 24];
ll que[2][2 << 24];
ll val[2][2 << 24];
ll cnt[2];
无论开不开 O2 优化都 无法通过,存在两个点 WA。
并且,第二个问题应该可以确定 不是测评机 的问题,因为在 本地/洛谷 IDE 都无法顺利通过第五组测试点。
这是我从未遇见过的问题,希望能有大佬帮我解决 QAQ。