题目大意

给定一个 行 列的棋盘，每个格子里有一个字符，红色（）或白色（）。你一开始要选择一个红色格子，每一步可以往上、下、左、右四个方向走，过程中到达的格子必须是红色的，每个格子只能经过一遍（这里指的经过一遍是严格意义上的，后面的移动过程中不能途经这个格子）。问你最多能走多少步，简而言之就是最长一笔画。特殊的，如果没有红色格子，答案为 。

前置知识

签到题，线性枚举即可，考虑到细节较多（队里一位场切紫题的大佬没调出来），评黄。

解法

• 发现只有 行，所以可以将棋盘分为 列，有四种情况（型号 ）：

1. （）

2. （）

3. （）

4. （）

• 如果相邻两列情况相同，就直接合并，所以最后会分成 个块，每个块有个 ，指包含多少列，相邻两个块型号不同。

• 考虑从左到右扫 到 ，记录两个变量 和 ，前者指通过当前块后的格子最大值（注意，这里两个变量都是格子数，最后减个 就是答案），后者是全局最大值。

• 两个白色格子（）直接清空 ，一红一白的情况也随便做，这里着重描述一下两个红，左右两边夹着两个一红一白（ 和 ）的情况。

• 如果前后两个一红一白的块，一个是 ，另一个是 （即型号不同），如果当前块的长度是偶数，说明当前块的格子可以全部走完， 直接加上；奇数，如果想要通过下一个快，那么最少最少要不能经过一个格子，不过下一个块还有一个格子，不亏，直接加。如果前后两个块型号相同，那么就是前面一种情况反过来，偶数减 奇数全加上。

• 然后就做完了，不过坑点比较多，对于一些人的代码别忘了把第 个块和 第 + 个块型号设为 （表示不存在），否则会出现错误。时间复杂度 ，与输入同阶，足以通过此题。

code

最后放上代码：

using namespace std;
const int NR = 1e6 + 1;
int n;
char mp[2][NR];
struct Node{
	int type, len;
}a[NR];
int cnt, maxn = 0;
int gettype(int i){
	if (mp[0][i] == 'R' && mp[1][i] == 'R') return 0;
	if (mp[0][i] == 'W' && mp[1][i] == 'W') return 1;
	if (mp[0][i] == 'R' && mp[1][i] == 'W') return 2;
	return 3;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n;
	for (int i = 0; i <= 1; i++)
		for (int j = 1; j <= n; j++)
			cin >> mp[i][j];
	a[++cnt] = (Node){gettype(1), 1};
	for (int i = 2; i <= n; i++){
		int t = gettype(i);
		if (t == a[cnt].type) a[cnt].len++;
		else a[++cnt] = (Node){t, 1};
	}
	a[0] = (Node){-1, -1};
	a[cnt + 1] = (Node){-1, -1};
	int ans = 0;
	for (int i = 1; i <= cnt; i++){
		int len = a[i].len;
		if (a[i].type == 0){
			maxn = max(maxn, ans + len * 2);
			if (len % 2 == 0){
				if (a[i - 1].type == 1) ans += len * 2;
				else if (a[i - 1].type == 2){
					if (a[i + 1].type == 1) ans += len * 2;
					else if (a[i + 1].type == 2) ans += len * 2;
					else if (a[i + 1].type == 3) ans += len * 2 - 1;
					else ans += len * 2;
				}
				else if (a[i - 1].type == 3){
					if (a[i + 1].type == 1) ans += len * 2;
					else if (a[i + 1].type == 2) ans += len * 2 - 1;
					else if (a[i + 1].type == 3) ans += len * 2;
					else ans += len * 2;
				}
				else ans += len * 2;
			}
			else{
				if (a[i - 1].type == 1) ans += len * 2;
				else if (a[i - 1].type == 2){
					if (a[i + 1].type == 1) ans += len * 2;
					else if (a[i + 1].type == 2) ans += len * 2 - 1;
					else if (a[i + 1].type == 3) ans += len * 2;
					else ans += len * 2;
				}
				else if (a[i - 1].type == 3){
					if (a[i + 1].type == 1) ans += len * 2;
					else if (a[i + 1].type == 2) ans += len * 2;
					else if (a[i + 1].type == 3) ans += len * 2 - 1;
					else ans += len * 2;
				}
				else ans += len * 2;
			}
		}
		else if (a[i].type == 1){
			ans = 0;
		}
		else if (a[i].type == 2){
			if (a[i - 1].type == 0){
				ans += len;
				maxn = max(maxn, ans);
			}
			else if (a[i - 1].type == 1){
				ans = len;
				maxn = max(maxn, ans);
			}
			else if (a[i - 1].type == 3){
				ans = len;
				maxn = max(maxn, ans);
			}
			else{
				ans += len;
				maxn = max(maxn, ans);
			}
		}
		else if (a[i].type == 3){
			if (a[i - 1].type == 0){
				ans += len;
				maxn = max(maxn, ans);
			}
			else if (a[i - 1].type == 1){
				ans += len;
				maxn = max(maxn, ans);
			}
			else if (a[i - 1].type == 2){
				ans = len;
				maxn = max(maxn, ans);
			}
			else{
				ans += len;
				maxn = max(maxn, ans);
			}
		}
	}
	if (maxn > 0) maxn--;
	cout << maxn << endl;
	return 0;
}

THE END