minesweeper
题意简述
说：
考虑决定每个点，发现决定了一个点可以删去周围一圈的边，对于两个独立的连通块实际上可以独立处理，由于是平面图，搜索不好卡。
代码
#include<bits/stdc++.h>
#define ll long long
#define LL __int128
#define dd double
using namespace std;
char gc(){static char buf[1<<16],*s,*t;if(s==t){t=(s=buf)+fread(buf,1,1<<16,stdin);if(s==t)return EOF;}return *s++;}
//#define getchar gc
ll read()
{
char c;
ll w=1;
while((c=getchar())>'9'||c<'0')if(c=='-')w=-1;
ll ans=c-'0';
while((c=getchar())>='0'&&c<='9')ans=(ans<<1)+(ans<<3)+c-'0';
return ans*w;
}
void pc(char c,int op)
{
static char buf[1<<16],*s=buf,*t=buf+(1<<16);
(op||((*s++=c)&&s==t))&&(fwrite(buf,1,s-buf,stdout),s=buf);
}
void wt(int x)
{
if(x>9)wt(x/10);
pc('0'+x%10,0);
}
void wts(int x,char op)
{
if(x<0)pc('-',0),x=-x;
wt(x);pc(op,0);
}
namespace ppprrr{const int xx=2,mod=2;ll ksm(ll a,ll b){ll ans=1;while(b){if(b&1)ans*=a,ans%=mod;a*=a,a%=mod,b>>=1;}return ans;}
ll jiec[xx],ni[xx];
ll C(ll n,ll m){return jiec[n]*ni[m]%mod*ni[n-m]%mod;}
void pre()
{
jiec[0]=1;
for(int i=1;i<xx;i++)jiec[i]=jiec[i-1]*i%mod;
ni[xx-1]=ksm(jiec[xx-1],mod-2);
for(int i=xx-2;i>=0;i--)ni[i]=ni[i+1]*(i+1)%mod;
}
int prim[xx],mn[xx],Cnt;
void pre(int n)
{
for(int i=2;i<=n;i++)
{
if(!mn[i])mn[i]=i,prim[++Cnt]=i;
for(int j=1;j<=Cnt;j++)
{
if(prim[j]*i>n)break;
mn[i*prim[j]]=prim[j];
if(i%prim[j]==0)break;
}
}
}
int lb(int x){return x&-x;}
ll sum[xx];
void Add(int x,int y){for(;x<xx;x+=lb(x))sum[x]+=y;}
ll ask(int x){ll ans=0;for(;x;x-=lb(x))ans+=sum[x];return ans;}
struct nod{int next,to;}e[xx<<1];
int cnt,h[xx];
void add(int x,int y){cnt++,e[cnt]={h[x],y},h[x]=cnt;}
}
int gcd(int a,int b){return !b?a:gcd(b,a%b);}
const int xx=1e6+5,mod=998244353;
void ad(int &a,int b){(a+=b)>=mod?a-=mod:0;}
ll ksm(ll a,ll b)
{
ll ans=1;
while(b)
{
if(b&1)ans*=a,ans%=mod;
a*=a,a%=mod,b>>=1;
}
return ans;
}
struct pr{int x,y;bool operator<(const pr&w)const{return x==w.x?y<w.y:x<w.x;};};
int n,m,k,q,a[xx],b[xx];
char s[505][505];
char is[505][505];
char Is[505][505];
int dx[]={1,1,1,-1,-1,-1,0,0},dy[]={1,0,-1,1,0,-1,1,-1};
int bel[505][505],tt,sz;
vector<pr>v;
set<int> A[505][505];
void dfs(int x,int y)
{
if(x<1||y<1||x>n||y>m)return;
// cerr<<x<<" "<<y<<"%%\n";
if(is[x][y])bel[x][y]=tt,A[x][y].insert(tt);
// ,cerr<<x<<" "<<y<<"%%\n";
sz+=is[x][y];
int cr=is[x][y];
is[x][y]=-1;
if(!cr)
{
for(int k=0;k<8;k++)
if(is[x+dx[k]][y+dy[k]]!=-1)dfs(x+dx[k],y+dy[k]);
else if(bel[x+dx[k]][y+dy[k]]!=tt&&Is[x+dx[k]][y+dy[k]]==1)
{
v.push_back({min(tt,bel[x+dx[k]][y+dy[k]]),max(tt,bel[x+dx[k]][y+dy[k]])});
// v.push_back({x+dx[k],y+dy[k]});
A[x+dx[k]][y+dy[k]].insert(tt);
}
}
}
bool operator==(const pr&a,const pr&b)
{
return !(a<b)&&!(b<a);
}
namespace sou
{
#define ull unsigned ll
const int xx=305;
struct nod{int next,to,v;}e[xx<<1];
int cnt,h[xx];
int d[xx];
void add(int x,int y,int z){/*cerr<<x<<" "<<y<<"%%\n"*/d[y]++;cnt++,e[cnt]={h[x],y,z},h[x]=cnt;}
mt19937 G(218);
int is[xx];
void D(ull &S,int x,vector<int>&v)
{
S|=(1ull<<x),v.push_back(x);
for(int i=h[x];i;i=e[i].next)if(!is[e[i].to]&&!(S>>e[i].to&1))D(S,e[i].to,v);
}
ll sum[xx];
int ct=0;
ull dfs(ull S)
{
++ct;
ull tt=0;
int x=__builtin_ctzll(S&-S);
// cerr<<x<<" "<<sum[x]<<"$%$\n";
if(__builtin_popcountll(S)==1)
return 1+ksm(2,sum[x]);
vector<int>lin;
D(tt,x,lin);
if(tt!=S)return dfs(tt)*dfs(tt^S)%mod;
int mx=0;
for(auto it:lin)if(d[it]>mx)mx=d[it],x=it;
if(d[x]<2)shuffle(lin.begin(),lin.end(),G),x=*lin.begin();
ull ans=0;
//填 1
is[x]=1;
for(int i=h[x];i;i=e[i].next)
if(!is[e[i].to])d[e[i].to]--;
ans+=dfs(S^(1ull<<x));
is[x]=0;
for(int i=h[x];i;i=e[i].next)
if(!is[e[i].to])d[e[i].to]++;
//填 0
is[x]=1;
for(int i=h[x];i;i=e[i].next)
if(!is[e[i].to])d[e[i].to]--,sum[e[i].to]+=e[i].v;
ans+=dfs(S^(1ull<<x))*ksm(2,sum[x])%mod;
is[x]=0;
for(int i=h[x];i;i=e[i].next)
if(!is[e[i].to])d[e[i].to]++,sum[e[i].to]-=e[i].v;
// cerr<<ans<<"qqweqe\n";
return ans;
}
map<pair<int,int>,int>mp;
void solve(int ct2)
{
// for(int i=1;i<=n;i++)
// for(int j=1;j<=m;j++)
// {
// assert(A[i][j].size()<=2);
// if(A[i][j].size())cerr<<A[i][j].size()<<"$$\n";
// }
// cerr<<n<<" "<<m<<"$$\n";
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
assert(A[i][j].size()<=2);
// if(A[i][j].size())cerr<<A[i][j].size()<<"$$\n";
// cerr<<i<<" "<<j<<"$%$%\n";
if(A[i][j].size()==1)
{
sum[*A[i][j].begin() -1]++;
}
else if(A[i][j].size()==2)
{
mp[make_pair(*A[i][j].begin() -1,*--A[i][j].end() -1)]++;
}
}
}
for(auto it:mp)
{
add(it.first.first,it.first.second,it.second);
add(it.first.second,it.first.first,it.second);
}
ll ans=dfs((1ull<<tt) -1);
// for(int i=0;i<tt;i++)cout<<i<<" "<<d[i]<<" "<<sum[i]<<"##\n";
// cerr<<ans<<"$$\n";
cout<<ans*ksm(2,ct2)%mod<<"\n";
}
}
int main(){
read();
n=read(),m=read();
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
char c;
while((c=getchar())!='.'&&c!='*');
s[i][j]=c;
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(s[i][j]=='*')
{
for(int k=0;k<8;k++)
is[i+dx[k]][j+dy[k]]=Is[i+dx[k]][j+dy[k]]=1;
}
}
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)if(s[i][j]=='*')is[i][j]=Is[i][j]=2;
ll ans=1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(!is[i][j])
{
++tt,sz=0;
dfs(i,j);
ans*=(ksm(2,sz)+1);
ans%=mod;
}
}
}
sort(v.begin(),v.end());
ll mx=0,cE=0;
pr lst={0,0};
for(auto it:v)
{
if(it==lst)++cE;
else cE=1;
lst=it;
mx=max(mx,cE);
}
// for(auto it:v)cout<<it
int te=v.size();
v.resize(unique(v.begin(),v.end(),[&](pr a,pr b){return !(a<b)&&!(b<a);})-v.begin());
// assert(te==v.size());
// if(v.size())assert(0);
// assert(cE<=2);
// assert(v.size()<=70);
int ct2=0;//是否有雷
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(is[i][j]==2)ct2=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(is[i][j]==1)++ct2;
if(!v.size())
{
cout<<ans*ksm(2,ct2)%mod<<"\n";
exit(0);
}
else
// if(v.size()<=60)
{
sou::solve(ct2);
exit(0);
}
pc('1',1);
return 0;
}