#include #include #include #include #include #include using namespace std; typedef long long llint; typedef pair pii; int n, m, k; char type; int in_city[20][20]; vector submasks[1500]; int dp[20][20][1500]; int solve(int y, int x, int mask) { int &ref = dp[y][x][mask]; if (ref != -1) return ref; if (in_city[y][x] != -1 && ((1 << in_city[y][x]) & mask)) { mask ^= (1 << in_city[y][x]); } if (mask == 0) return 0; ref = 1e9; for (auto subms : submasks[mask]) { ref = min(ref, solve(y, x, subms.first) + solve(y, x, subms.second)); } if (type == 'R' || type == 'Q') { for (int i = 0; i < n; ++i) { ref = min(ref, solve(i, x, mask) + 1); } for (int i = 0; i < m; ++i) { ref = min(ref, solve(y, i, mask) + 1); } } if (type == 'B' || type == 'Q') { for (int i = -20; i <= 20; ++i) { if (y + i >= 0 && y + i < n && x + i >= 0 && x + i < m) { ref = min(ref, solve(y + i, x + i, mask) + 1); } if (y - i >= 0 && y - i < n && x + i >= 0 && x + i < m) { ref = min(ref, solve(y - i, x + i, mask) + 1); } } } if (type == 'K') { for (int i = -1; i <= 1; ++i) { for (int j = -1; j <= 1; ++j) { if (y + i >= 0 && y + i < n && x + j >= 0 && x + j < m) { ref = min(ref, solve(y + i, x + j, mask) + 1); } } } } if (type == 'N') { for (int i = -2; i <= 2; ++i) { for (int j = -2; j <= 2; ++j) { int ai = abs(i); int aj = abs(j); int has1 = ai == 1 || aj == 1; int has2 = ai == 2 || aj == 2; if (has1 && has2) { if (y + i >= 0 && y + i < n && x + j >= 0 && x + j < m) { ref = min(ref, solve(y + i, x + j, mask) + 1); } } } } } return ref; } int main(void) { pii king; scanf("%d%d", &n, &m); scanf("%d%d %c", &king.first, &king.second, &type); --king.first; --king.second; scanf("%d", &k); memset(in_city, -1, sizeof in_city); for (int i = 0; i < k; ++i) { int y, x; scanf("%d%d", &y, &x); --y; --x; in_city[y][x] = i; } memset(dp, -1, sizeof(dp)); for (int mask = 0; mask < (1 << k); ++mask) { for (int submask = 1; submask < (1 << k); ++submask) { if ((submask | mask) == mask) { int other_submask = submask ^ mask; if (other_submask > submask) continue; submasks[mask].emplace_back(submask, other_submask); } } } int ans = solve(king.first, king.second, (1 << k) - 1); if (ans == 1e9) { printf("%d\n", -1); } else { printf("%d\n", ans); } return 0; }