复杂度是$O(n^2)$ RT

#include<bits/stdc++.h>
#include<deque>
#define int long long
using namespace std;

int n; char arr[510][510];

int ans;
int ans1, ans2;
struct node{
	int x, y, bu;
};

deque<node> que, que2; 

int vis[510][510];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

void bfs() {
	int bx, by, ex, ey;
	bx = 1, by = 1, ex = n, ey = n;
	if(arr[bx][by] == 'R') {
		que.push_back({bx, by, 0});
	} else {
		que.push_back({bx, by, 1});
	}
	while(!que.empty()) {
		node tp = que.front(); que.pop_front();
		if(tp.x == ex and tp.y == ey) {
			ans1 = tp.bu;
			break;
		}
		vis[tp.x][tp.y] = 1;
		for(int i=0; i<4; ++i) {
			int tox, toy;
			tox = tp.x + dx[i];
			toy = tp.y + dy[i];
			if(vis[tox][toy] or tox < 1 or tox > n or toy < 1 or toy > n) {
				continue;
			} 
			if(arr[tox][toy] == 'R') {
				node temp = {tox, toy, tp.bu};
				que.push_front(temp);
			} else {
				node temp = {tox, toy, tp.bu+1};
				que.push_back(temp);
			}
		}
	}
	memset(vis, 0, sizeof vis);
	bx = 1, by = n; ex = n, ey = 1;
	if(arr[bx][by] == 'B') {
		que2.push_back({bx, by, 0});
	} else {
		que2.push_back({bx, by, 1});
	}
	while(!que2.empty()) {
		node tp = que2.front(); que2.pop_front();
		if(tp.x == ex and tp.y == ey) {
			ans2 = tp.bu;
			break;
		}
		vis[tp.x][tp.y] = 1;
		for(int i=0; i<4; ++i) {
			int tox, toy;
			tox = tp.x + dx[i];
			toy = tp.y + dy[i];
			if(vis[tox][toy] or tox < 1 or tox > n or toy < 1 or toy > n) {
				continue;
			} 
			if(arr[tox][toy] == 'B') {
				node temp = {tox, toy, tp.bu};
				que2.push_front(temp);
			} else {
				node temp = {tox, toy, tp.bu+1};
				que2.push_back(temp);
			}
		}
	}
	ans = ans1 + ans2;
}

signed main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for(int i=1; i<=n; ++i) {
		for(int j=1; j<=n; ++j) {
			cin >> arr[i][j];
		}
	}
	bfs();
	cout << ans;
	return 0;
}