P5297题解
前言
这道题是之前刷大模拟的时候找到的（别问我为什么现在才写问就是太菜了)。
题目挺有意思的，也是一道比较好的 2-SAT 问题。
另外推销一下 blog，同时感谢一下学长 H6_6Q。
正文
前置芝士
- 2-SAT（可以参考模板P4782)。
- 比较强大的代码能力。
一定的物理学知识。（大概初二就行？视调 bug 如归的决心。
题目分析
首先我们需要看出这道题目是一个 2-SAT 问题。
这咋和 2-SAT 扯上关系了呢？
首先我们可以注意到一个特殊的性质：每个格子在横向和竖向上最多会被一个炮塔打到。
考虑感性理解一下：
我们把炮塔击中空地看作是一束来自空地的激光击中炮塔和，一束来自炮塔的激光击中空地，由于光路可逆，所以两束分别来自空地和炮塔激光共用同一条路径，只是方向相反。而如果从另一侧也击中了该空地，那么接下来这一束来自另一侧的激光也可以沿着从空地击中原炮塔的路径击中原炮塔。而对于同侧的情况来看，光的路径一定是唯一确定的，所以两束能在同方向上击中同一块空地的激光的路径必定存在真包含关系，即必有一束激光击中另一个炮塔，故证毕（感觉这块有点难理解，可以画个图思考一下，还是挺显然的）。
所以你™扯了这一堆和 2-SAT 有啥关系？
嗯？
每个格子在横向和竖向上最多会被一个炮塔打到？
每个格子必须被至少一个炮塔打到？
这不就是 x[i]=1 or x[j]=1 吗？
那直接套 2-SAT 板子好了。
Code
有一说一，这题的代码还是挺恶心的。
首先我们记录一个 batid 数组，batid[i][j] 表示在第 i 行第 j 列的炮塔编号，如果此处没有炮塔则编号为 0 。同时我们开一个 vector，里面记录炮塔的位置和编号，方便以后遍历。
int n,m,batid[MAXN][MAXN],_cnt;
char Map[MAXN][MAXN];
struct BATT{int x,y,id;BATT(int _x,int _y,int _id){x=_x,y=_y,id=_id;}};
vector<BATT>bat;
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>Map[i][j];
if(Map[i][j]=='-'||Map[i][j]=='|'){
bat.pb(BATT(i,j,++_cnt));
batid[i][j]=_cnt;
}
}
}
然后对于每一个炮塔的横竖两种状态进行深搜。为了方便直接复制 2-SAT 板子起见，把横向记为 0 ，纵向记为 1 ，如果该炮塔激光消失的位置为障碍或场地边缘，返回 true，否则为 false。对于每个炮塔经历的空地，我们新建一个二维 vector infl， infl[id][dire] 表示能打到该位置的炮塔编号和方向。
struct VISI{int id,dire;VISI(int _id,int _dire){id=_id,dire=_dire;}};
vector<VISI>infl[55][55];
bool dfs(int x,int y,int d,int id,int k,int from){
if(x<1||y<1||x>n||y>m) return 1;
if(Map[x][y]=='#') return 1;
if(Map[x][y]=='/'){d=(d!=0?d!=1?d!=2?2:3:0:1);return dfs(x+dx[d],y+dy[d],d,id,0,from);}
if(Map[x][y]=='\\'){d=(d!=0?d!=1?d!=2?0:1:2:3);return dfs(x+dx[d],y+dy[d],d,id,0,from);}
if(Map[x][y]=='.'||k){infl[x][y].pb(VISI(id,(from+1)%2));return dfs(x+dx[d],y+dy[d],d,id,0,from);}
if(Map[x][y]=='-'||Map[x][y]=='|') return 0;
}
接下来进行第一遍 check 判断是否有炮塔既不能横向摆放也不能竖向摆放，如有直接输出 -1 ,定义 can 数组，can[id][dire] 表示编号为 id 的炮塔能否摆在 dire 方向上。若炮塔 id' 只能沿 dire' 方向摆放，则添加约束条件 x[id]=dire or x[id]=dire。对于每个空地而言，如果空地被 id 号炮塔在 dire 方向上击中且 can[id][dire]=1 则称该炮塔对空地有影响。记录四个数值分别为 fid,fn,sid,sn 分别表示第一个、第二个能影响到该空地的炮塔编号，若 fid=0 ，即没有炮塔可以影响该空地，输出-1，若 sid=0，即只有一个炮塔影响该空地，添加约束条件 x[fid]=fn or x[fid]=fn。否则添加约束条件 x[fid]=fn or x[sid]=sn。
void solve(){
for(BATT now:bat){
can[now.id][0]=(dfs(now.x,now.y,1,now.id,1,1)&dfs(now.x,now.y,3,now.id,1,3));
can[now.id][1]=(dfs(now.x,now.y,0,now.id,1,0)&dfs(now.x,now.y,2,now.id,1,2));
if(!(can[now.id][0]|can[now.id][1])){
puts("IMPOSSIBLE");
return;
}else{
if(!can[now.id][0])res.pb(REST(now.id,now.id,1,1));
else if(!can[now.id][1])res.pb(REST(now.id,now.id,0,0));
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(Map[i][j]!='.')continue;
int fid=0,sid=0,fn=0,sn=0;
for(VISI k:infl[i][j]){
if(can[k.id][k.dire]){
if(!fid)fid=k.id,fn=k.dire;
else sid=k.id,sn=k.dire;
}
}
if(!fid){
puts("IMPOSSIBLE");
return;
}else if(!sid){
res.pb(REST(fid,fid,fn,fn));
}else{
res.pb(REST(fid,sid,fn,sn));
}
}
}
solve_2_SAT();
return;
}然后就是 2-SAT 模板了
void solve_2_SAT(){
for(REST R:res){
int id1=R.id1,id2=R.id2,res1=R.res1,res2=R.res2;
add_edge(id1+_cnt*res1,id2+_cnt*(!res2));
add_edge(id2+_cnt*res2,id1+_cnt*(!res1));
}
for(int i=1;i<=(_cnt<<1);i++){
if(!dfn[i]){
tarjan(i);
}
}
for(int i=1;i<=_cnt;i++){//别跟我一样把<=打成<
if(type[i]==type[i+_cnt]){
puts("IMPOSSIBLE");
return;
}
}
puts("POSSIBLE");
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(!batid[i][j]){
printf("%c",Map[i][j]);continue;
}
printf("%c",type[batid[i][j]]>type[batid[i][j]+_cnt]?'-':'|');
}
puts("");
}
}最后上一发完整 Code
#include<bits/stdc++.h>
#define re register
#define il inline
#define pb push_back
using namespace std;
const int dx[5]={1,0,-1,0},dy[5]={0,-1,0,1},MAXN=55,MAXB=555;
int t,n,m,batid[MAXN][MAXN],head[MAXB],tot,sta[MAXB],type[MAXB],dfn[MAXB],low[MAXB],top,tmp,_cnt,cnt;
char Map[MAXN][MAXN];
bool can[MAXB][3],insta[MAXB];
struct BATT{int x,y,id;BATT(int _x,int _y,int _id){x=_x,y=_y,id=_id;}};
struct REST{int id1,id2,res1,res2;REST(int _id1,int _id2,int _res1,int _res2){id1=_id1,id2=_id2,res1=_res1,res2=_res2;}};
struct VISI{int id,dire;VISI(int _id,int _dire){id=_id,dire=_dire;}};
struct Edge{int from,to,next;}e[MAXB<<7];
vector<VISI>infl[55][55];
vector<BATT>bat;
vector<REST>res;
void add_edge(int u,int v){e[++tot].to=v,e[tot].from=u,e[tot].next=head[u],head[u]=tot;}
void tarjan(int x){
dfn[x]=low[x]=++cnt,insta[x]=1,sta[++top]=x;
for(int i=head[x];i;i=e[i].next){
int y=e[i].to;
if(!dfn[y]) tarjan(y),low[x]=min(low[x],low[y]);
else if(insta[y]) low[x]=min(low[x],dfn[y]);
}
if(dfn[x]==low[x]){
tmp++;
do{
type[sta[top]]=tmp;
insta[sta[top]]=0;
top--;
}while(x!=sta[top+1]);
}
return;
}
void solve_2_SAT(){
for(REST R:res){
int id1=R.id1,id2=R.id2,res1=R.res1,res2=R.res2;
add_edge(id1+_cnt*res1,id2+_cnt*(!res2));
add_edge(id2+_cnt*res2,id1+_cnt*(!res1));
}
for(int i=1;i<=(_cnt<<1);i++){
if(!dfn[i]){
tarjan(i);
}
}
for(int i=1;i<=_cnt;i++){
if(type[i]==type[i+_cnt]){
puts("IMPOSSIBLE");
return;
}
}
puts("POSSIBLE");
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(!batid[i][j]){
printf("%c",Map[i][j]);continue;
}
printf("%c",type[batid[i][j]]>type[batid[i][j]+_cnt]?'-':'|');
}
puts("");
}
}
bool dfs(int x,int y,int d,int id,int k,int from){
if(x<1||y<1||x>n||y>m) return 1;
if(Map[x][y]=='#') return 1;
if(Map[x][y]=='/'){d=(d!=0?d!=1?d!=2?2:3:0:1);return dfs(x+dx[d],y+dy[d],d,id,0,from);}
if(Map[x][y]=='\\'){d=(d!=0?d!=1?d!=2?0:1:2:3);return dfs(x+dx[d],y+dy[d],d,id,0,from);}
if(Map[x][y]=='.'||k){infl[x][y].pb(VISI(id,(from+1)%2));return dfs(x+dx[d],y+dy[d],d,id,0,from);}
if(Map[x][y]=='-'||Map[x][y]=='|') return 0;
}
void solve(){
for(BATT now:bat){
can[now.id][0]=(dfs(now.x,now.y,1,now.id,1,1)&dfs(now.x,now.y,3,now.id,1,3));
can[now.id][1]=(dfs(now.x,now.y,0,now.id,1,0)&dfs(now.x,now.y,2,now.id,1,2));
if(!(can[now.id][0]|can[now.id][1])){
puts("IMPOSSIBLE");
return;
}else{
if(!can[now.id][0])res.pb(REST(now.id,now.id,1,1));
else if(!can[now.id][1])res.pb(REST(now.id,now.id,0,0));
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(Map[i][j]!='.')continue;
int fid=0,sid=0,fn=0,sn=0;
for(VISI k:infl[i][j]){
if(can[k.id][k.dire]){
if(!fid)fid=k.id,fn=k.dire;
else sid=k.id,sn=k.dire;
}
}
if(!fid){
puts("IMPOSSIBLE");
return;
}else if(!sid){
res.pb(REST(fid,fid,fn,fn));
}else{
res.pb(REST(fid,sid,fn,sn));
}
}
}
solve_2_SAT();
return;
}
void init(){
memset(Map,0,sizeof(Map));
memset(batid,0,sizeof(batid));
memset(low,0,sizeof(low));
memset(dfn,0,sizeof(dfn));
memset(insta,0,sizeof(insta));
memset(head,0,sizeof(head));
memset(can,0,sizeof(can));
memset(type,0,sizeof(type));
bat.clear();
res.clear();
for(int i=1;i<=tot;i++){
e[i].from=0;
e[i].to=0;
e[i].next=0;
}
tot=0,top=0,tmp=0,cnt=0,_cnt=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
infl[i][j].clear();
}
}
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>Map[i][j];
if(Map[i][j]=='-'||Map[i][j]=='|'){
bat.pb(BATT(i,j,++_cnt));
batid[i][j]=_cnt;
}
}
}
}
int main(){
scanf("%d",&t);
while(t--){
init();
solve();
}
return 0;
}εnd
最后求个赞呗（逃