迷宫（maze）

【from new_dtoj 3990: 迷宫（maze）】 题目描述 迷宫可以抽象成一个矩阵，小K要从（1，1）走到（N，M），而且只能往下和往右走，即小K只能从（X，Y）走到（X，Y+1）和（X+1，Y）。小K不能走出迷宫（即X>N或Y>M）。当然，迷宫有一些格子是被堵住的，小K不能从这些格子经过。 每个没被堵住的格子都有一个权值，小K十分喜欢X这个数字和异或这个运算。所以他希望所有他经过的格子的异或和为X。现在小K想知道他有多少种走法，听说你是一位大佬蒟蒻 ，于是他向你求助。 N,M<=20,Ai<=1e9 题解 考场正解，细节错误，数据太强只有暴力分 因为从起点直接往终点dfs会超时，所以我们分成两半来做 第一次从起点走到对角线就不走了，然后在对角线统计前一部分的答案 然后再从终点往前走，碰到对角线就统计最后答案，数据太小可以过 效率$O(2^n\ast n)$ 具体细节见代码

#include <cstdio> #include <vector> #include <algorithm> using namespace std; int n,m,k,a[25][25],d[25][25],ax,f[25][25][10005]; long long ans;vector<int>p[405]; void D1(int x,int y,int s){ if (x+y==(n+m)/2+1){ p[d[x][y]].push_back(s); return; } if (x<n && a[x+1][y]) D1(x+1,y,s^a[x][y]); if (y<n && a[x][y+1]) D1(x,y+1,s^a[x][y]); } void D2(int x,int y,int s){ if (x+y==(n+m)/2+1){ int t=s^k,l=d[x][y]; int k1=upper_bound(p[l].begin(),p[l].end(),t)-p[l].begin(); int k2=lower_bound(p[l].begin(),p[l].end(),t)-p[l].begin(); ans=ans+k1-k2;return; } if (x>1 && a[x-1][y]) D2(x-1,y,s^a[x-1][y]); if (y>1 && a[x][y-1]) D2(x,y-1,s^a[x][y-1]); } int main(){ scanf("%d%d%d",&n,&m,&k); for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) scanf("%d",&a[i][j]),ax=max(a[i][j],ax),d[i][j]=(i-1)*m+j; D1(1,1,0); for (int i=1;i<=d[n][m];i++) sort(p[i].begin(),p[i].end()); D2(n,m,a[n][m]); printf("%lld\n",ans); return 0; }