Observe that since Ash always completes his journey in minimum total time, he never visits the same city twice. In other words, the string formed the ash is a path.
Suppose the ash starts his journey from cell (0,j) , visits every cell to its left and comes to cell (0,0) , then visits cell (1,0) and every cell to its right to cell (1,j). Now there are two possible options for the Ash if he wishes to visit each cell.
1.He can move right to cell (1,n-1), visiting all cells in between, and then go up to cell (0,n-1). From there visit all cells to its left until it reaches cell (0,j+1) thereby completing the tour.
2.Otherwise he can move to cell (1,j+1) followed by a move to cell (0,j+1) . In this case there are again two possible options for Ash. Move from cell (0,j+1) to cell (0,j+2) followed by a move to cell (1,j+2) and have two choices again. Or visit all cells to its right , move down and visit all remaining cells to its left.
Note that he can start from cell (1,j) instead of cell (0,j) . Also, he can start from column j, visit every cell to its right, move down/up and visit every cell to its left until it reaches column j again and repeat the same procedure with two choices as elaborated before. So we need to handle these cases as well with a similar strategy as described.
C++ code -
C++
#include <bits/stdc++.h>
#define forn(i, n) for(int i = 0; i < int(n); ++i)
using namespace std;
typedef long long li;
typedef long double ld;
const li MOD = li(1e18) + 31;
const li BASE = li(1e9) + 9;
const int N = 5000 + 5;
int n;
char s[2][N];
li bpw[N];
li hl[2][N], hr[2][N], hz[2][N];
li mul(li a, li b) {
li q = li(ld(a) * b / MOD);
li r = a * b - q * MOD;
while (r < 0)
r += MOD;
while (r >= MOD)
r -= MOD;
return r;
}
li add(li a, li b) {
a += b;
if (a >= MOD)
a -= MOD;
return a;
}
li sub(li a, li b) {
a -= b;
if (a < 0)
a += MOD;
return a;
}
void pchash(string s, li *h) {
h[0] = 0;
forn(i, s.size())
h[i + 1] = add(mul(h[i], BASE), s[i]);
}
li chash(li *h, int l, int len) {
return sub(h[l + len], mul(h[l], bpw[len]));
}
string rev(string s) {
reverse(s.begin(), s.end());
return s;
}
void solve() {
assert(scanf("%d", &n) == 1);
assert(1 <= n && n <= 600);
forn(i, 2) {
assert(scanf("%s", s[i]) == 1);
cerr << n << " " << s[i] << endl;
assert((int) strlen(s[i]) == n);
}
vector
forn(_, 2) {
pchash(rev(s[0]) + s[1], hl[0]);
pchash(rev(s[1]) + s[0], hl[1]);
pchash(s[0] + rev(s[1]), hr[0]);
pchash(s[1] + rev(s[0]), hr[1]);
forn(k, 2) {
string t;
forn(i, n)
forn(j, 2)
t.push_back(s[(k ^ i ^ j) & 1][i]);
pchash(t, hz[k]);
}
forn(r, 2) {
forn(c, n) {
li h = chash(hl[r], n - c - 1, 2 * (c + 1));
for (int len = 0; c + 1 + len <= n; len++) {
int pos = c + 1;
li ch = mul(h, bpw[2 * len]);
ch = add(ch, chash(hz[(r ^ pos ^ 1) & 1], 2 * pos, 2 * len));
pos += len;
ch = mul(ch, bpw[2 * (n - pos)]);
ch = add(ch, chash(hr[(r ^ 1 ^ len) & 1], pos, 2 * (n - pos)));
all.push_back(ch);
}
}
}
forn(i, 2)
reverse(s[i], s[i] + n);
}
sort(all.begin(), all.end());
all.erase(unique(all.begin(), all.end()), all.end());
printf("%d\n", (int) all.size());
}
int main() {
bpw[0] = 1;
forn(i, N - 1)
bpw[i + 1] = mul(bpw[i], BASE);
int T;
assert(scanf("%d", &T) == 1);
assert(1 <= T && T <= 15);
forn(i, T)
solve();
return 0;
}