【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(2n∗n)O(2^n*n)O(2n∗n)

具体细节见代码

#include 
    
     #include 
     
      #include 
      
       using namespace std;int n,m,k,a[25][25],d[25][25],ax,f[25][25][10005];long long ans;vector
       
        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
        
         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;}