小N最近喜歡玩一款塔防游戲。

題目描述

這款游戲的棋盤是一個?n×m?的網格，每個格子上會有以下類型物件：

1. A 型炮臺：會向上下兩個方向同時發射激光，符號為?|;
2. B 型炮臺：會向左右兩個方向同時發射激光，符號為?-;
3. 空地：激光穿過該物件會保持方向前進，符號為?.;
4. 障礙：激光到達該物件會消失，符號為?#;
5. 正反射鏡：激光到達該物件后，會依物理定律改變方向，但仍繼續前進，符號為?\;
6. 副反射鏡：激光到達該物件后，會依物理定律改變方向，但仍繼續前進，符號為?/;

注意激光之間可以互相穿過，但如果激光射出網格邊界，也會消失。
小 N 是一個強迫癥玩家，他想讓每一處空地都會被至少一束激光打到，但不能讓激光攻擊到自己的炮臺以致損壞。
小 N 可以將任意多的 A 型炮臺改造成 B 型炮臺，也可以把任意多的 B 型炮臺改造成 A 型炮臺。
你可以告訴他能否通過這些改造實現他的目標嗎?

輸入格式

第一行一個正整數?T，表示數據組數。
每組數據第一行有兩個正整數?n,m。
接下來?n?行，每行一個長度為?m?的字符串，表示棋盤。

輸出格式

對于每組數據，若無解則輸出一行?IMPOSSIBLE，否則輸出一行?POSSIBLE，再輸出改造后的棋盤。
如果有多組解，輸出任意一個即可。

思路：

首先?n,m≤50，暴力枚舉每個炮臺的朝向是不可取的，但可以分別計算每個炮臺每種朝向能打到的格子。不難想到，能打到自己炮臺的炮臺朝向一定是不可取的。

題目又說道，要求每一處空地都會被至少一束激光打到，那我們需要看每一處空地可能被哪些炮臺的哪些朝向打到。

接下來是題目的核心，每一處空地最多可能被哪些炮臺的哪些可取的朝向打到呢？?首先，空地不會被兩束同向的激光打到，因為若可能，它們必有重合的一段路徑，然而其中一束激光會被路徑上的炮臺或反射鏡所影響。

舉個例子：

-.\.
....
-.\.
....

此圖中對于空地?(4,3)，若上方除?(3,1)?的激光打來，一定會碰到反射鏡而改變路徑。

其次，空地也不會被兩束反向的激光打到，因為光路可逆，若可能，一束激光能打到空地，則一定能沿著反向打到該空地的激光的逆光路，打到另一個炮臺。

還是通過舉例說明：

-..\
....
.-./

此圖中兩束激光均能打到?(2,4)?的空地，且方向相反，不難發現它們必能互相打到。

綜上所述，再根據抽屜原理，每個空地最多可能被兩個炮臺的可取的朝向打到。?又因為至少被一束激光打到。所以，每個空地均可被看作?i 炮臺為橫/豎向?或?j 炮臺為橫/豎向?的約束條件。 這里就能看出是 2-SAT 問題了，根據前文所述，用 2-SAT 模板的處理方法即可。

代碼細節

思路是簡明且重要的，并且代碼細節難度也不容小覷?（畢竟是黑題

認為自己的代碼實現思路是清晰且完備的，下面進行展示。

• 遍歷激光的路徑使用 dfs，除了建立方向數組，再建立兩個數組?lf[],rf[]?代表每種激光方向經過副/主反射鏡后改變成的方向，這樣能簡便地處理反射的問題。

const int dx[]={0,-1,0,1},dy[]={-1,0,1,0},lf[]={3,2,1,0},rf[]={1,0,3,2};
...
bool dfs(int x,int y,int dir){int xx=x+dx[dir],yy=y+dy[dir];if(mp[xx][yy]=='#'||xx<1||xx>n||yy<1||yy>m)return 1;if(mp[xx][yy]=='/')return dfs(xx,yy,lf[dir]);if(mp[xx][yy]=='\\')return dfs(xx,yy,rf[dir]);if(mp[xx][yy]=='.')return dfs(xx,yy,dir);return 0;
}

• 對于每個朝向，先 dfs 一次判斷是否能打到其他炮臺，能則說明朝向不合法，建一條選該朝向指向選另外朝向的邊，體現選該朝向就能推出矛盾。否則朝向合法，再進行一次 dfs 尋找能打到的空地。這里用?i?表示橫向，用?i+tcnt?表示豎向。

	for(int i=1;i<=tcnt;i++){if(!dfs(towx[i],towy[i],0)||!dfs(towx[i],towy[i],2))add(i,i+tcnt);else{dfs2(i,towx[i],towy[i],0);dfs2(i,towx[i],towy[i],2);}if(!dfs(towx[i],towy[i],1)||!dfs(towx[i],towy[i],3))add(i+tcnt,i);else{dfs2(i+tcnt,towx[i],towy[i],1);dfs2(i+tcnt,towx[i],towy[i],3);}}

• 接下來遍歷每處空地建邊，注意分類討論：

• 若空地不能被任何激光打到，直接無解。

• 若空地只能被一個炮臺的朝向打到，建一條不選該朝向指向選該朝向的邊，體現該朝向不得不選。

• 若空地能被兩個炮臺的朝向打到，就是常規的 2-SAT，分別建??i→j?和??j→i?的邊。

這里定義了一個函數?opp?表示相反朝向對應的編號。

		for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(mp[i][j]=='.'){int sz=S[i][j].size();if(sz==0)add(1,tcnt+1),add(tcnt+1,1);if(sz==1)add(opp(S[i][j][0]),S[i][j][0]);if(sz==2){if(opp(S[i][j][0])!=S[i][j][1])add(opp(S[i][j][0]),S[i][j][1]),add(opp(S[i][j][1]),S[i][j][0]);}}}}

至此，本題的所有代碼難點都過去了，接下來正常地跑 Tarjan，通過強連通分量編號確定每個炮臺的朝向即可

?代碼
?

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#define N 5010
#define M N<<1
using namespace std;
int T,n,m;
int low[N],dfn[N],scc[N],num,cnt,towx[N],towy[N],tcnt,flag;
int h[N],nxt[M],ver[M],tot,st[N],top;
const int dx[]={0,-1,0,1},dy[]={-1,0,1,0},lf[]={3,2,1,0},rf[]={1,0,3,2};
char mp[55][55];
vector<int>S[55][55];
void init(){num=cnt=tcnt=top=0,tot=-1,flag=1;memset(h,-1,sizeof(h)); memset(dfn,0,sizeof(dfn));memset(scc,0,sizeof(scc));for(int i=1;i<=n;i++){for(int j=1;j<=m;j++)S[i][j].clear();}
}
void add(int x,int y){ver[++tot]=y;nxt[tot]=h[x];h[x]=tot;
}
int opp(int x){return x<=tcnt?x+tcnt:x-tcnt;
}
bool dfs(int x,int y,int dir){int xx=x+dx[dir],yy=y+dy[dir];if(mp[xx][yy]=='#'||xx<1||xx>n||yy<1||yy>m)return 1;if(mp[xx][yy]=='/')return dfs(xx,yy,lf[dir]);if(mp[xx][yy]=='\\')return dfs(xx,yy,rf[dir]);if(mp[xx][yy]=='.')return dfs(xx,yy,dir);return 0;
}
void dfs2(int id,int x,int y,int dir){int xx=x+dx[dir],yy=y+dy[dir];if(mp[xx][yy]=='#'||xx<1||xx>n||yy<1||yy>m)return ;if(mp[xx][yy]=='/')dfs2(id,xx,yy,lf[dir]);if(mp[xx][yy]=='\\')dfs2(id,xx,yy,rf[dir]);if(mp[xx][yy]=='.')S[xx][yy].push_back(id),dfs2(id,xx,yy,dir);
}
void tarjan(int u){st[++top]=u;low[u]=dfn[u]=++num;for(int i=h[u];~i;i=nxt[i]){int v=ver[i];if(!dfn[v]){tarjan(v);low[u]=min(low[v],low[u]);}else if(!scc[v])low[u]=min(dfn[v],low[u]);}if(low[u]==dfn[u]){++cnt;while(1){int v=st[top--];scc[v]=cnt;if(v==u)break;}}
}
int main(){scanf("%d",&T);while(T--){scanf("%d%d",&n,&m);init();for(int i=1;i<=n;i++){scanf("%s",mp[i]+1);for(int j=1;j<=m;j++){if(mp[i][j]=='-'||mp[i][j]=='|')towx[++tcnt]=i,towy[tcnt]=j;}}for(int i=1;i<=tcnt;i++){if(!dfs(towx[i],towy[i],0)||!dfs(towx[i],towy[i],2))add(i,i+tcnt);else{dfs2(i,towx[i],towy[i],0);dfs2(i,towx[i],towy[i],2);}if(!dfs(towx[i],towy[i],1)||!dfs(towx[i],towy[i],3))add(i+tcnt,i);else{dfs2(i+tcnt,towx[i],towy[i],1);dfs2(i+tcnt,towx[i],towy[i],3);}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(mp[i][j]=='.'){int sz=S[i][j].size();if(sz==0)add(1,tcnt+1),add(tcnt+1,1);if(sz==1)add(opp(S[i][j][0]),S[i][j][0]);if(sz==2){if(opp(S[i][j][0])!=S[i][j][1])add(opp(S[i][j][0]),S[i][j][1]),add(opp(S[i][j][1]),S[i][j][0]);}}}}for(int i=1;i<=2*tcnt;i++){if(!dfn[i])tarjan(i);}for(int i=1;i<=tcnt;i++){if(scc[i]==scc[i+tcnt]){printf("IMPOSSIBLE\n");flag=0;break;}}if(flag){printf("POSSIBLE\n");for(int i=1;i<=tcnt;i++){if(scc[i]>scc[i+tcnt])mp[towx[i]][towy[i]]='|';else mp[towx[i]][towy[i]]='-';}for(int i=1;i<=n;i++){printf("%s\n",mp[i]+1);}}}return 0;
}