import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; import java.util.StringTokenizer; /** * ICPC Central Europe Regional Contest 2018 * Sample solution: Trees Gump * * This is a straightforward translation of one of the C++ solution. */ public class KingTranslated { StringTokenizer st = new StringTokenizer(""); BufferedReader input = new BufferedReader(new InputStreamReader(System.in)); boolean hasNextToken() { try { while (!st.hasMoreTokens()) { String line = input.readLine(); if (line == null) return false; st = new StringTokenizer(line); } } catch (IOException ex) { throw new RuntimeException(ex); } return true; } String nextToken() { return (!hasNextToken()) ? null : st.nextToken(); } int nextInt() { return Integer.parseInt(nextToken()); } public static void main(String[] args) { System.out.println(new KingTranslated().run()); } static final int MAXS = 16, MAXT = 11, INF = 100000007; int[][] km = new int [][]{{-2, -1}, {-2, 1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2}, {2, -1}, {2, 1}}; int n, m, sx, sy, t, ts, vcnt; char c; int[][] d = new int[MAXS*MAXS][MAXS*MAXS], dp = new int[MAXS*MAXS][1 << MAXT]; List terms = new ArrayList<>(); int gv (int x, int y) { return x * m + y; } boolean isv (int x, int y) { return (x >= 0 && x < n && y >= 0 && y < m); } int run() { //load grid structure n = nextInt(); m = nextInt(); vcnt = n * m; for (int i = 0; i < vcnt; ++i) for (int j = 0; j < vcnt; ++j) d[i][j] = INF; for (int i = 0; i < vcnt; ++i) d[i][i] = 0; //load terminals sx = nextInt(); sy = nextInt(); c = nextToken().charAt(0); --sx;--sy; terms.add(gv(sx, sy)); t = nextInt(); for (int i = 0; i < t; ++i) { int x = nextInt(), y = nextInt(); --x;--y; terms.add(gv(x, y)); if (c == 'B' && ((sx + sy) % 2) != ((x + y) % 2)) return -1; } ts = terms.size(); //translate grid->graph if (c == 'K') { for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) { for (int di = -1; di < 2; ++di) for (int dj = -1; dj < 2; ++dj) if (isv(i + di, j + dj)) { int x = gv(i,j); int y = gv(i + di, j + dj); if (x != y) d[x][y] = d[y][x] = 1; } } } else if (c == 'R') { for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) { for (int di = -1; di < 2; ++di) for (int dj = -1; dj < 2; ++dj) if (di * di + dj * dj == 1) { int cm = 0; while (isv(i + di * cm, j + dj * cm)) { int x = gv(i,j); int y = gv(i + di * cm, j + dj * cm); if (x != y) d[x][y] = d[y][x] = 1; ++cm; } } } } else if (c == 'Q') { for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) { for (int di = -1; di < 2; ++di) for (int dj = -1; dj < 2; ++dj) if (di * di + dj * dj > 0) { int cm = 0; while (isv(i + di * cm, j + dj * cm)) { int x = gv(i,j); int y = gv(i + di * cm, j + dj * cm); if (x != y) d[x][y] = d[y][x] = 1; ++cm; } } } } else if (c == 'B') { for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) { for (int di = -1; di < 2; ++di) for (int dj = -1; dj < 2; ++dj) if (di * di + dj * dj > 1) { int cm = 0; while (isv(i + di * cm, j + dj * cm)) { int x = gv(i,j); int y = gv(i + di * cm, j + dj * cm); if (x != y) d[x][y] = d[y][x] = 1; ++cm; } } } } else { for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) { for (int k = 0; k < 8; ++k) if (isv(i + km[k][0], j + km[k][1])) { int x = gv(i,j); int y = gv(i + km[k][0], j + km[k][1]); if (x != y) d[x][y] = d[y][x] = 1; } } } //fw for (int k = 0; k < vcnt; ++k) for (int i = 0; i < vcnt; ++i) for (int j = 0; j < vcnt; ++j) d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]); //steiner for (int i = 0; i < vcnt; ++i) for (int j = 0; j < (1< 0; submask = (submask - 1) & mask) { dp[i][mask] = Math.min(dp[i][mask], dp[i][submask] + dp[i][mask - submask]); } for (int j = 0; j < vcnt; ++j) dp[j][mask] = Math.min(dp[j][mask], dp[i][mask] + d[i][j]); } } //get result int res = dp[gv(sx, sy)][(1 << ts) - 1]; return (res < INF) ? res : -1; } }