P3869 [TJOI2009] 宝藏 题解

· · 题解

Problem

题目大意：给你一张地图，其中有 N 个机关，每个机关踩一次可以使对应的地方的格子内让能走变成不能走，或者是不能走变成能走，问从 S 到 T 的最少步数。

数据范围： n,m \leq 30,N \leq 10。

Solution

看到 N \leq 10，可以想到肯定是运用状态压缩来记录每个状态已经触发了哪些机关奇数次（偶数次等于每触发）。

再因为是棋盘问题，还是最优步数，可以想到是搜索。而查找最优步数那必然是广搜好很多。所以我们可以定义一个状态为 \{x,y,dep,k\}，表示当前在 x,y 处，已走了 dep 步，且当前机关触发奇数次状态为 k，进行广搜即可。

每要到一个地方时，可以看看所有机关中有没有影响这个地方的，若影响了奇数次，那么就不能走（若本身为 # ，那么也要记一次，用异或可以快速解决）；同时判断一下走了这一步之后会不会触发什么机关，记得更新状态（异或解决）。

两个注意点：

  1. 是从 S 到 T 而不要想当然的以为是 1,1 到 n,n （可能只有我会犯这么低级的错误吧 qwq）；

  2. 要记忆化搜索，不然会 MLE（队列里面空间会炸），若 x,y,k 已被访问过，那么就不再访问。

Code

代码如下：

#include<bits/stdc++.h>
using namespace std;
int n,m,N,stx,sty;
struct hl{
    int a,b,x,y;
}t[11];
char mp[32][32];
string s;
struct len{
    int x,y,dep,k;
}tmp;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
bool vis[32][32][1<<12];
queue<len> q;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        cin>>s;s='?'+s;
        for(int j=1;j<=m;j++) 
        {
            mp[i][j]=s[j];
            if(mp[i][j]=='S') stx=i,sty=j;
        }
    }
    scanf("%d",&N);
    for(int i=1;i<=N;i++) scanf("%d%d%d%d",&t[i].a,&t[i].b,&t[i].x,&t[i].y);
    q.push((len){stx,sty,0,0});
    vis[stx][sty][0]=true;
    while (!q.empty())
    {
        tmp=q.front();q.pop();
        if(mp[tmp.x][tmp.y]=='T')
        {
            printf("%d\n",tmp.dep);
            return 0;
        }
        for(int i=0;i<4;i++)
        {
            int xx=tmp.x+dx[i],yy=tmp.y+dy[i];
            if(xx<1||xx>n||yy<1||yy>m) continue;
            int flag,kk=tmp.k;
            if(mp[xx][yy]=='#') flag=0;
            else flag=1;
            for(int j=1;j<=N;j++)
            {
                if(xx==t[j].x&&yy==t[j].y&&((tmp.k>>j-1)&1)) flag^=1;
                if(xx==t[j].a&&yy==t[j].b) kk^=(1<<j-1);
            }
            if(flag&&!vis[xx][yy][kk]) 
            {
                vis[xx][yy][kk]=true;
                q.push((len){xx,yy,tmp.dep+1,kk});
            }
        }
    }

}