1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131
| #include <bits/stdc++.h> using namespace std;
const int maxn = 5e1 + 5, maxk = 7; const int ch_d[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
struct node { int x, y, d; long long st, stp; long long pas[4]; char mp[maxn][maxn]; };
int n, m, k, xx, yy; node a[maxk]; int book[maxn][maxn][4]; int dir[256]; long long mst, ans = LLONG_MAX, llcm = 1, sum = 1; long long moshu[maxk], yushu[maxk];
long long lcm(long long a, long long b) { return a / __gcd(a, b) * b; }
void calc(int id) { memset(book, 0, sizeof book); book[a[id].x][a[id].y][a[id].d] = 1; while (true) { if (a[id].x == xx && a[id].y == yy) a[id].pas[a[id].d] = book[a[id].x][a[id].y][a[id].d]; int td = ((a[id].d + a[id].mp[a[id].x][a[id].y]) & 3), tx = a[id].x + ch_d[td][0], ty = a[id].y + ch_d[td][1]; if (tx < 1 || tx > n || ty < 1 || ty > m) { td = ((td + 2) & 3); tx = a[id].x + ch_d[td][0]; ty = a[id].y + ch_d[td][1]; } if (book[tx][ty][td]) { a[id].st = book[tx][ty][td]; a[id].stp = book[a[id].x][a[id].y][a[id].d] + 1 - book[tx][ty][td]; return; } book[tx][ty][td] = book[a[id].x][a[id].y][a[id].d] + 1; a[id].x = tx; a[id].y = ty; a[id].d = td; } }
long long cal() { long long res = yushu[1]; long long lllcm = moshu[1]; for (int i = 2; i <= k; i++) { int cnt = 0; while (res % moshu[i] != yushu[i]) { res += lllcm; res %= llcm; if (++cnt > moshu[i]) return LLONG_MAX; } lllcm = lcm(lllcm, moshu[i]); } while (res < mst) res += llcm; return res; }
void doit(int id) { if (id == k + 1) { ans = min(ans, cal()); return; } for (int i = 0; i < 4; i++) { if (a[id].pas[i] < a[id].st) continue; moshu[id] = a[id].stp; yushu[id] = a[id].pas[i] % a[id].stp; doit(id + 1); } }
int main() { dir['U'] = 0; dir['R'] = 1; dir['D'] = 2; dir['L'] = 3; scanf("%d %d %d", &n, &m, &k); scanf("%d %d", &xx, &yy); for (int i = 1; i <= k; i++) { char ch; scanf("%d %d %c", &a[i].x, &a[i].y, &ch); a[i].d = dir[ch]; for (int j = 1; j <= n; j++) { scanf("%s", a[i].mp[j] + 1); for (int l = 1; l <= m; l++) a[i].mp[j][l] -= 48; } calc(i); if (!(a[i].pas[0] || a[i].pas[1] || a[i].pas[2] || a[i].pas[3])) { printf("-1\n"); return 0; } } for (int i = 1; i <= k; i++) { mst = max(mst, a[i].st); llcm = lcm(llcm, a[i].stp); } for (long long i = 0; i <= mst; i++) { bool flag = true; for (int j = 1; j <= k; j++) { bool f = false; for (int l = 0; l < 4; l++) { if (a[j].pas[l] == 0) continue; if (a[j].pas[l] < a[j].st) { if (a[j].pas[l] == i) { f = true; break; } } else if (i >= a[j].pas[l] && i % a[j].stp == a[j].pas[l] % a[j].stp) { f = true; break; } } if (f == false) { flag = false; break; } } if (flag) { printf("%lld\n", i); return 0; } } doit(1); if (ans == LLONG_MAX) printf("-1\n"); else printf("%lld\n", ans); return 0; }
|