萌新求助,WA50,不知道哪里错了
查看原帖
萌新求助,WA50,不知道哪里错了
122641
GIFBMP楼主2022/8/13 20:15
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;
const int MAXM = 3e5 + 10 ;
int T , n , m , fir[510] , tot ;
struct edge {
	int to , nxt ;
} e[MAXM << 1] ;
void add (int u , int v) {
	e[++tot].to = v ; e[tot].nxt = fir[u] ; fir[u] = tot ;
}
char s[55][55] ;
int dx[4] = {0 , 1 , 0 , -1} , dy[4] = {1 , 0 , -1 , 0} ; 
int p[55][55] , vis[55][55][2] , cnt , a[55][55][2] , t[55][55] , v2[55][55] , nx[510] , ny[510] ;
int dfs (int x , int y , int p , int d) {
	vis[x][y][p] = 1 ;
	int tx = x + dx[d] , ty = y + dy[d] ;
	if (tx < 1 || tx > n || ty < 1 || ty > m || s[tx][ty] == '#') return 1 ;
	if (s[tx][ty] == '|' || s[tx][ty] == '-') return 0 ;
	if (s[tx][ty] == '.') return dfs (tx , ty , p , d) ;
	else if (s[tx][ty] == '/') return dfs (tx , ty , p , 3 - d) ;
	else return dfs (tx , ty , p , d ^ 1) ;
}
int dfn[510] , low[510] , st[510] , tp , cc , col[510] , vv[510] , cco ;
void tarjan (int x) {
	dfn[x] = low[x] = ++cc ; st[++tp] = x ; vv[x] = 1 ;
	for (int i = fir[x] , v = e[i].to ; i ; i = e[i].nxt , v = e[i].to) {
		if (!dfn[v]) tarjan (v) , low[x] = min (low[x] , low[v]) ;
		else if (vv[v]) low[x] = min (low[x] , dfn[v]) ;
	}
	if (dfn[x] == low[x]) {
		col[x] = ++cco ; vv[x] = 0 ;
		for (; st[tp] != x ; tp--) col[st[tp]] = cco , vv[st[tp]] = 0 ;
		tp-- ;
	}
}
int main () {
	scanf ("%d" , &T) ;
	while (T--) {
		memset (p , 0 , sizeof (p)) ;
		memset (fir , 0 , sizeof (fir)) ;
		memset (a , 0 , sizeof (a)) ;
		memset (t , 0 , sizeof (t)) ;
		memset (col , 0 , sizeof (col)) ;
		memset (vv , 0 , sizeof (vv)) ;
		memset (dfn , 0 , sizeof (dfn)) ;
		memset (low , 0 , sizeof (low)) ;
		tot = cnt = 0 ; bool flag = 0 ;
		scanf ("%d%d" , &n , &m) ;
		for (int i = 1 ; i <= n ; i++) scanf ("%s" , s[i] + 1) ;
		for (int i = 1 ; i <= n && !flag ; i++)
			for (int j = 1 ; j <= m ; j++) {
				if (s[i][j] != '|' && s[i][j] != '-') continue ;
				memset (vis , 0 , sizeof (vis)) ;
				p[i][j] = ++cnt ; nx[cnt] = i , ny[cnt] = j ;
				int t1 = dfs (i , j , 0 , 0) & dfs (i , j , 0 , 2) ;
				int t2 = dfs (i , j , 1 , 1) & dfs (i , j , 1 , 3) ;
				if (!t1 && !t2) {flag = 1 ; break ;}
				if (!t1) {
					for (int k = 1 ; k <= n ; k++)	
						for (int l = 1 ; l <= m ; l++)
							if (s[k][l] == '.' && vis[k][l][1])
								a[k][l][t[k][l]++] = 2 * cnt + 1 ;
					add (2 * cnt , 2 * cnt + 1) ;
					continue ;
				}
				if (!t2) {
					for (int k = 1 ; k <= n ; k++)
						for (int l = 1 ; l <= m ; l++)
							if (s[k][l] == '.' && vis[k][l][0])
								a[k][l][t[k][l]++] = 2 * cnt ;
					add (2 * cnt + 1 , 2 * cnt) ;
					continue ;
				}
				for (int k = 1 ; k <= n ; k++)
					for (int l = 1 ; l <= m ; l++)
						if (s[k][l] == '.') {
							if (vis[k][l][0] && vis[k][l][1]) v2[k][l] = 1 ;
							else if (vis[k][l][0]) a[k][l][t[k][l]++] = 2 * cnt ;
							else if (vis[k][l][1]) a[k][l][t[k][l]++] = 2 * cnt + 1 ;
						}
			}
		for (int i = 1 ; i <= n && !flag ; i++)
			for (int j = 1 ; j <= m ; j++) {
				if (s[i][j] != '.' || v2[i][j]) continue ;
				if (!t[i][j]) {flag = 1 ; break ;}
				if (t[i][j] == 1) add (a[i][j][0] ^ 1 , a[i][j][0]) ;
				else add (a[i][j][0] ^ 1 , a[i][j][1]) , add (a[i][j][1] ^ 1 , a[i][j][0]) ;
			}
		if (flag) {puts ("IMPOSSIBLE") ; continue ;}
		tp = cco = cc = 0 ;
		for (int i = 2 ; i <= 2 * cnt + 1 ; i++)
			if (!dfn[i]) tarjan (i) ;
		for (int i = 1 ; i <= cnt ; i++)
			if (col[2 * i] == col[2 * i + 1]) {flag = 1 ; break ;}
		if (flag) {puts ("IMPOSSIBLE") ; continue ;}
		puts ("POSSIBLE") ;
		for (int i = 1 ; i <= n ; i++ , puts (""))
			for (int j = 1 ; j <= m ; j++) {
				if (s[i][j] != '|' && s[i][j] != '-') putchar (s[i][j]) ;
				else putchar (col[2 * p[i][j]] > col[2 * p[i][j] + 1] ? '|' : '-') ;
			}
	}
	return 0 ;
}
2022/8/13 20:15
加载中...