#include <bits/stdc++.h> using namespace std; #ifdef D #define DEBUG(x) \ do { \ x \ cout.flush(); \ } while (0) #else #define DEBUG(x) #endif const int NMAX = 1e6 + 7; int n, m, q, tt, a, b, x, y, io; vector<vector<int>> t; vector<vector<string>> s; vector<vector<int>> vis; bool ok; void dfs(int vy, int vx) { vis[vy][vx] = io; if (vx == x && vy == y) { ok = 1; return; } // w prawo if (vx < m) { if (vis[vy][vx + 1] < io) { if (vy < n && s[vy][vx][tt % s[vy][vx].size()] == '1') { // dolne dfs(vy, vx + 1); } else if (vy > 0 && s[vy - 1][vx][tt % s[vy - 1][vx].size()] == '1') { // gorne dfs(vy, vx + 1); } } } // w lewo if (vx > 0) { if (vis[vy][vx - 1] < io) { if (vy < n && s[vy][vx - 1][tt % s[vy][vx - 1].size()] == '1') { // dolne dfs(vy, vx - 1); } else if (vy > 0 && s[vy - 1][vx - 1][tt % s[vy - 1][vx - 1].size()] == '1') { // gorne dfs(vy, vx - 1); } } } // w dol if (vy < n) { if (vis[vy + 1][vx] < io) { if (vx < m && s[vy][vx][tt % s[vy][vx].size()] == '0') { // prawe dfs(vy + 1, vx); } else if (vx > 0 && s[vy][vx - 1][tt % s[vy][vx - 1].size()] == '0') { // lewe dfs(vy + 1, vx); } } } // w gore if (vy > 0) { if (vis[vy - 1][vx] < io) { if (vx < m && s[vy - 1][vx][tt % s[vy - 1][vx].size()] == '0') { // prawe dfs(vy - 1, vx); } else if (vx > 0 && s[vy - 1][vx - 1][tt % s[vy - 1][vx - 1].size()] == '0') { // lewe dfs(vy - 1, vx); } } } } void solve() { ok = 0; io++; dfs(b, a); while (!ok) { io++; tt++; for (int i = 0; i <= n && !ok; ++i) { for (int j = 0; j <= m && !ok; ++j) { if (vis[i][j] == io - 1) { dfs(i, j); } } } } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> m >> q; t.resize(n); s.resize(n); vis.resize(n + 1); vis[n].resize(m + 1); for (int i = 0; i < n; ++i) { t[i].resize(m); s[i].resize(m); vis[i].resize(m + 1); for (int j = 0; j < m; ++j) { cin >> s[i][j]; } } for (int i = 0; i < q; ++i) { cin >> tt >> b >> a >> y >> x; solve(); cout << tt << "\n"; } return 0; }
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 | #include <bits/stdc++.h> using namespace std; #ifdef D #define DEBUG(x) \ do { \ x \ cout.flush(); \ } while (0) #else #define DEBUG(x) #endif const int NMAX = 1e6 + 7; int n, m, q, tt, a, b, x, y, io; vector<vector<int>> t; vector<vector<string>> s; vector<vector<int>> vis; bool ok; void dfs(int vy, int vx) { vis[vy][vx] = io; if (vx == x && vy == y) { ok = 1; return; } // w prawo if (vx < m) { if (vis[vy][vx + 1] < io) { if (vy < n && s[vy][vx][tt % s[vy][vx].size()] == '1') { // dolne dfs(vy, vx + 1); } else if (vy > 0 && s[vy - 1][vx][tt % s[vy - 1][vx].size()] == '1') { // gorne dfs(vy, vx + 1); } } } // w lewo if (vx > 0) { if (vis[vy][vx - 1] < io) { if (vy < n && s[vy][vx - 1][tt % s[vy][vx - 1].size()] == '1') { // dolne dfs(vy, vx - 1); } else if (vy > 0 && s[vy - 1][vx - 1][tt % s[vy - 1][vx - 1].size()] == '1') { // gorne dfs(vy, vx - 1); } } } // w dol if (vy < n) { if (vis[vy + 1][vx] < io) { if (vx < m && s[vy][vx][tt % s[vy][vx].size()] == '0') { // prawe dfs(vy + 1, vx); } else if (vx > 0 && s[vy][vx - 1][tt % s[vy][vx - 1].size()] == '0') { // lewe dfs(vy + 1, vx); } } } // w gore if (vy > 0) { if (vis[vy - 1][vx] < io) { if (vx < m && s[vy - 1][vx][tt % s[vy - 1][vx].size()] == '0') { // prawe dfs(vy - 1, vx); } else if (vx > 0 && s[vy - 1][vx - 1][tt % s[vy - 1][vx - 1].size()] == '0') { // lewe dfs(vy - 1, vx); } } } } void solve() { ok = 0; io++; dfs(b, a); while (!ok) { io++; tt++; for (int i = 0; i <= n && !ok; ++i) { for (int j = 0; j <= m && !ok; ++j) { if (vis[i][j] == io - 1) { dfs(i, j); } } } } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> m >> q; t.resize(n); s.resize(n); vis.resize(n + 1); vis[n].resize(m + 1); for (int i = 0; i < n; ++i) { t[i].resize(m); s[i].resize(m); vis[i].resize(m + 1); for (int j = 0; j < m; ++j) { cin >> s[i][j]; } } for (int i = 0; i < q; ++i) { cin >> tt >> b >> a >> y >> x; solve(); cout << tt << "\n"; } return 0; } |