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;
}