D - AB Graph (构造、图)

题目

思路：
分为两种情况：
1.当m为奇数时，直接12121212…构造出的一定是回文。
2.当m为偶数时，可以知道n>=3时一定可以构造出。证明如下：
当1，2，3三个点中出现来回字母一样，只需两个点不断循环即可。

当无上述情况，来回必然是a,b交叉，因此我们一定可以找到如下的图。其实就是有连续两个a，1->2->3->1,或2->3->1->2，或3->1->2->3，这几种情况aab,aaa,aba…因为是循环的一定可以找出两个连续的a构成下图。（不懂可以自行模拟下过程）

当(m/2)%2 == 1
我们可以按序号123212321232…走构造出aabbaabb…aabb，
当(m/2)%2==0
我们可以按序号232123212321走构造出
abbaabba…abba

Code:

#include<iostream>
using namespace std;
typedef long long ll;
const int Max = 1e3 + 5;
char lst[Max][Max];

int main()
{
   
	int t;cin >> t;
	while (t--)
	{
   
		int n, m;cin >> n >> m;
		for (int i = 1;i <= n;i++)
			for (int j = 1;j <= n;j++)cin>>lst[i][j];
		if (m % 2 == 1)
		{
   
			cout << "YES" << endl;
			for (int i = 1;i <= m + 1;i++)
				if (i % 2 == 0)cout << "1 ";
				else cout << "2 ";
			cout << endl;
		}
		else
		{
   
			if (n == 2)
			{
   
				if (lst[1][2] != lst[2][1])cout << "NO" << endl;
				else
				{
   
					cout << "YES" << endl;
					for (int i = 1;i <= m + 1;i++)
						if (i % 2 == 0)cout << "1 ";
						else cout << "2 ";
					cout << endl;
				}
			}
			else
			{
   
				cout<<"YES"<<endl;
				int a = 0, b, c;
				if (lst[1][2] == lst[2][1])a = 1, b = 2;
				else if (lst[2][3] == lst[3][2])a = 2, b = 3;
				else if (lst[1][3] == lst[3][1])a = 3, b = 1;
				if (a)
				{
   
					for (int i = 1;i <= m + 1;i++)
						if (i % 2 == 1)cout << a << " ";
						else cout << b << " ";
				}
				else
				{
   
					if (lst[1][2] == lst[2][3])a = 1, b = 2, c = 3;
					else if (lst[2][3] == lst[3][1])a = 2, b = 3, c = 1;
					else if (lst[3][1] == lst[1][2])a = 3, b = 1, c = 2;
					if (m / 2 % 2 == 1)
					{
   
						for (int i = 1;i <= m + 1;i++)
							if (i % 4 == 1)cout << a << " ";
							else if (i % 4 == 2)cout << b << " ";
							else if (i % 4 == 3)cout << c << " ";
							else cout << b << " ";
					}
					else
					{
   
						for (int i = 1;i <= m + 1;i++)
							if (i % 4 == 1)cout << b << " ";
							else if (i % 4 == 2)cout << c << " ";
							else if (i % 4 == 3)cout << b << " ";
							else cout << a << " ";
					}
				}
				cout << endl;
			}
		}
	}
}