洛谷：P2407 [SDOI2009]地图复原（标记欧拉回路）

洛谷：P2407 [SDOI2009]地图复原（标记欧拉回路） 地图复原

题意：

告诉你哪些地方转了弯、哪些地方走直线（不告诉方向），让你还原出初始的一个欧拉路径（环）

思路：

观察可以发现，任意一行的 " T " 的个数必定是偶数，为了形成回路，转过一个弯之后必定要转回来；同理任意一列也是一致，由此就可以模拟出一种必定满足的情况

代码：

#include
#include
#include
#define mem(a,b) memset(a,b,sizeof a)
#define cinios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
#define sca scanf
#define pri printf
#define ul (u << 1)
#define ur (u << 1 | 1)
#define x first
#define y second
//#pragma GCC optimize(2)
//[博客地址](https://blog.csdn.net/weixin_51797626?t=1) 
using namespace std;

typedef long long ll;
typedef pair PII;
typedef pair  PI;

const int N = 810, M = 200010, MM = N;
int INF = 0x3f3f3f3f, mod = 100003;
ll LNF = 0x3f3f3f3f3f3f3f3f;
int n, m, k, T, S, D;
char s[N][N];
int row[N][N], col[N][N];

int main() {
	cinios;

	cin >> n >> m;
	for (int i = 1; i <= n; i++)cin >> s[i] + 1;

	for (int i = 1; i <= n; i++) {
		int t = 0;
		for (int j = 1; j <= m; j++) {
			if (s[i][j] == 'T')t ^= 1;//每行奇数T和偶数T之间必定是路径
			row[i][j] = t;//标记
		}
	}

	for (int j = 1; j <= m; j++) {
		int t = 0;
		for (int i = 1; i <= n; i++) {
			col[i][j] = t; //每列也是一致，但要注意下下标，会影响输出
			if (s[i][j] == 'T')t ^= 1;
		}
	}

	for (int i = 1; i <= n; i++) { //输出是 2*n-1 行、2*m-1 列
		if (i > 1) {
			for (int j = 1; j <= m; j++)
				if (col[i][j])cout << "| ";//第二行开始画列路径
				else cout << "  ";
			cout << 'n';
		}

		for (int j = 1; j <= m; j++) {
			cout << "o";//点
			if (row[i][j])cout << "-";//行路径
			else cout << " ";
		}
		cout << 'n';
	}

	return 0;
}