题解 CF1006F 【Xor-Paths】

Wichiene · 2018-10-02 02:08:00 · 题解

第一个双向dfs

啊

题目翻译

有n*m的格子，从（1，1）走到（n，m），只能向下/右走。 每个格子上有权值，求走过格子的权值的异或和=k的方案数

（语文太差了我尽力了

从前往后搜，然后从后往前搜 到对角线上的点就停下，统计方案数

代码 ———————————————————————————————

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#include<cmath>
#include<map> 
#define ll long long
using namespace std;
map<ll,ll>mp[21][21];//我觉得int也可以emmmm
ll tot,k,a[21][21];
ll n,m;
void dfs(ll x1,ll y1,ll v1)//x1,y1:坐标；v1：异或和
{
    if(x1+y1==n+1)//对角线
    {
        mp[x1][y1][v1]++;//到这里，异或和是v
        return;
    }

    if(x1<n)dfs(x1+1,y1,v1^a[x1+1][y1]);
    if(y1<m)dfs(x1,y1+1,v1^a[x1][y1+1]);//往后搜
 } 
 void dfss(ll x2,ll y2,ll v2)
{
    if(x2+y2==n+1)
    {
        tot+=mp[x2][y2][v2^k^a[x2][y2]];
        //上一句：~~组织语言……emmm……弃疗~~
        //见下面吧。。。dalao随意。。。~~比我菜的真的有吗。。不写可以吗。。~~
        return;
    }
    if(x2>1)dfss(x2-1,y2,v2^a[x2-1][y2]);
    if(y2>1)dfss(x2,y2-1,v2^a[x2][y2-1]);//往前搜
 } 
int main()
{
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    cin>>a[i][j];
    dfs(1,1,a[1][1]);
    dfss(n,m,a[n][m]);//没了
    cout<<tot; 
}

上面的那个地方

1.不要把x1，y1..再。亦或。一遍。了。^的逆运算就是^, a^b^b=a. 还有a^b=c则a^c=b.

2.上面统计了到x1,y1的异或和为v1的方案数。我们就硬生生把它接起来，如果这次搜索到x1，y1的异或和为v1^k，那么就是有mp[x1][y1][v1]的方案了

3.没有3

另外，不用回溯也无所谓判重。毕竟他好像走不回来

再另外。。感谢一下wjh和zhn。。大佬