现在正在完美破防,求调。。
查看原帖
现在正在完美破防,求调。。
1163457
UncleEric楼主2024/11/8 19:40
#include<bits/stdc++.h>
using namespace std;
struct BAT{
	int x,y;
}bat[2505];
struct point{
	int id,pos;
};
int T,n,m,cnt,bid[55][55];
int dfn[5005],low[5005],dft,vis[5005];
int can[2505][2],col[5005],scccnt;
const int dx[4]={-1,0,1,0};
const int dy[4]={0,-1,0,1};
char mp[55][55];
vector<int> e[5005];
vector<point> info[55][55];
stack<int>stk;

inline bool dfs(int x,int y,int pos,int id,int from){
	if(x<1||x>n||y<1||y>m) return 1;
	if(mp[x][y]=='#') return 1;
	if(mp[x][y]=='/'){
		pos=pos^3;
		return dfs(x+dx[pos],y+dy[pos],pos,id,from);
	}
	if(mp[x][y]=='\\'){
		pos=pos^1;
		return dfs(x+dx[pos],y+dy[pos],pos,id,from);
	}
	if(mp[x][y]=='.'){
		info[x][y].push_back({id,from});
		return dfs(x+dx[pos],y+dy[pos],pos,id,from);
	}
	return 0;
}

inline void tarjan(int u){
	dfn[u]=low[u]=++dft;
	vis[u]=1;stk.push(u);
	for(int v:e[u]){
		if(!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);
		else if(vis[v]) low[u]=min(low[u],dfn[v]);
	}
	if(low[u]==dfn[u]){
		col[u]=++scccnt;
		while(1){
			int j=stk.top();stk.pop();
			vis[j]=0;if(j==u)break;
			col[j]=scccnt;
		}
	}
}

inline void sol(){
	cnt=0;dft=0;scccnt=0;
	memset(col,0,sizeof(col));
	memset(bid,0,sizeof(bid));
	memset(bat,0,sizeof(bat));
	memset(dfn,0,sizeof(dfn));
	memset(low,0,sizeof(low));
	memset(vis,0,sizeof(vis));
	memset(can,0,sizeof(can));
	for(int i=0;i<5000;i++)e[i].clear();
	for(int i=0;i<50;i++){
		for(int j=0;j<50;j++) info[i][j].clear();
	}
	while(!stk.empty())stk.pop();
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>mp[i][j];
			if(mp[i][j]=='-'||mp[i][j]=='|'){
				bat[++cnt]={i,j};
				bid[i][j]=cnt;
			}
		}
	}
	bool flag=1;
	for(int i=1;i<=cnt;i++){
		can[i][0]=(dfs(bat[i].x+dx[1],bat[i].y+dy[1],1,i,0)&dfs(bat[i].x+dx[3],bat[i].y+dy[3],3,i,0));
		can[i][1]=(dfs(bat[i].x+dx[2],bat[i].y+dy[2],2,i,1)&dfs(bat[i].x+dx[0],bat[i].y+dy[0],0,i,1));
		if(!(can[i][0]|can[i][1])){
			cout<<"IMPOSSIBLE\n";return;
		}
		if(!can[i][0]) e[i+cnt].push_back(i);
		else if(!can[i][1]) e[i].push_back(i+cnt);
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(mp[i][j]!='.') continue;
			int fid=0,sid=0,fn=0,sn=0;
			for(point k:info[i][j]){
				if(can[k.id][k.pos]){
					if(!fid) fid=k.id,fn=k.pos;
					else sid=k.id,sn=k.pos;
				}
			}
			if(!fid){
				cout<<"IMPOSSIBLE\n";return;
			}else if(sid){
				e[fid+cnt*fn].push_back(sid+cnt*(sn^1));
				e[sid+cnt*sn].push_back(fid+cnt*(fn^1));
			}else{
				e[fid+cnt*fn].push_back(fid+cnt*(fn^1));
			}
		}
	}
	for(int i=1;i<=2*cnt;i++){
		if(!dfn[i]) tarjan(i);
	}
	for(int i=1;i<=cnt;i++){
		if(col[i]==col[i+cnt]){
			cout<<"IMPOSSIBLE\n";return;
		}
	}
	cout<<"POSSIBLE\n";
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(bid[i][j]){
				cout<<(col[bid[i][j]]>col[bid[i][j]+cnt]?'-':'|');
			}else cout<<mp[i][j];
		}cout<<'\n';
	}	
}

int main(){
//	freopen("test.in","r",stdin);
//	freopen("test.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>T;
	while(T--){
		sol();
	}
	return 0;
}
2024/11/8 19:40
加载中...