#include <iostream> #include <map> #include <vector> #include <stack> #include <algorithm> using namespace std; const long long mod = 1'000'000'007; vector<vector<int>> shift_up(vector<vector<int>>&v) { int n = v.size(), m = v[0].size(); vector<vector<int>>answer(n, vector<int>(m, -1)); for(int j = 0; j < m; j++) { stack<int>s; for(int i = 0; i < n; i++) { if(v[i][j] > -1) { s.push(v[i][j]); } } while(!s.empty()) { answer[(int)s.size() - 1][j] = s.top(); s.pop(); } } return answer; } vector<vector<int>> shift_down(vector<vector<int>>&v) { int n = v.size(), m = v[0].size(); vector<vector<int>>answer(n, vector<int>(m, -1)); for(int j = 0; j < m; j++) { stack<int>s; for(int i = n - 1; i >= 0; i--) { if(v[i][j] > -1) { s.push(v[i][j]); } } while(!s.empty()) { answer[n - (int)s.size()][j] = s.top(); s.pop(); } } return answer; } vector<vector<int>> shift_left(vector<vector<int>>&v) { int n = v.size(), m = v[0].size(); vector<vector<int>>answer(n, vector<int>(m, -1)); for(int i = 0; i < n; i++) { stack<int>s; for(int j = 0; j < m; j++) { if(v[i][j] > -1) { s.push(v[i][j]); } } while(!s.empty()) { answer[i][(int)s.size() - 1] = s.top(); s.pop(); } } return answer; } vector<vector<int>> shift_right(vector<vector<int>>&v) { int n = v.size(), m = v[0].size(); vector<vector<int>>answer(n, vector<int>(m, -1)); for(int i = 0; i < n; i++) { stack<int>s; for(int j = m - 1; j >= 0; j--) { if(v[i][j] > -1) { s.push(v[i][j]); } } while(!s.empty()) { answer[i][m - (int)s.size()] = s.top(); s.pop(); } } return answer; } void print(vector<vector<int>>&grid) { map<int, char>char_by_id = {{-1, '.'}, {1, 'B'}, {2, 'C'}}; for(vector<int>row : grid) { for(int x : row) { cout << char_by_id[x]; } cout << '\n'; } } void apply(vector<vector<int>>&grid, char c) { switch(c) { case 'L': grid = shift_left(grid); break; case 'P': grid = shift_right(grid); break; case 'G': grid = shift_up(grid); break; case 'D': grid = shift_down(grid); break; } } void apply(vector<vector<int>>&grid, string s) { for(char c : s) apply(grid, c); } vector<vector<int>>combine(vector<vector<int>>a, vector<vector<int>>b) { int n = a.size(), m = a[0].size(); vector<vector<int>>answer(n, vector<int>(m)); for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { int x = b[i][j] / m, y = b[i][j] % m; answer[i][j] = a[x][y]; } } return answer; } vector<vector<int>>raise(vector<vector<int>>&v, int k) { if(k == 1) return v; vector<vector<int>>answer = raise(v, k / 2); answer = combine(answer, answer); if(k % 2 == 1) answer = combine(answer, v); return answer; } int main() { ios_base::sync_with_stdio(0); int n, m; cin >> n >> m; vector<vector<int>>grid(n, vector<int>(m)); for(int i = 0; i < n; i++) { string s; cin >> s; for(int j = 0; j < m; j++) { switch(s[j]) { case '.': grid[i][j] = -1; break; case 'B': grid[i][j] = 1; break; case 'C': grid[i][j] = 2; break; } } } map<char, int>orientation = {{'L', 0}, {'P', 0}, {'G', 1}, {'D', 1}}; int k, i; cin >> k; string s; cin >> s; vector<char>last(2, -1); vector<int>cnt(2, 0); for(i = 0; i < k - 1; i++) { if(orientation[s[i]] != orientation[s[i + 1]]) { apply(grid, s[i]); apply(grid, s[i + 1]); last[orientation[s[i]]] = s[i]; last[orientation[s[i + 1]]] = s[i + 1]; cnt[0] = cnt[1] = 1; break; } } // cout << "grid\n"; // print(grid); // cout << '\n'; if(i == k - 1) { apply(grid, s[k - 1]); print(grid); return 0; } vector<char>cyclic; for(i += 2; i < k; i++) { while(i < k - 1 && orientation[s[i + 1]] == orientation[s[i]]) i++; if(last[orientation[s[i]]] == s[i]) { continue; } last[orientation[s[i]]] = s[i]; if(!cyclic.empty() && orientation[cyclic.back()] == orientation[s[i]]) { cyclic.pop_back(); if(cnt[orientation[s[i]]] == 1) { cyclic.push_back(s[i]); } else { cnt[orientation[s[i]]]--; } } else { cnt[orientation[s[i]]]++; cyclic.push_back(s[i]); } // cout << "cyclic = "; // for(char c : cyclic) // cout << c << ' '; // cout << '\n'; } /* cout << "cyclic = "; for(char c : cyclic) cout << c << ' '; cout << '\n';*/ if(cyclic.size() >= 4) { string pattern = ""; for(int i = 0; i < 4; i++) pattern += string(1, cyclic[i]); vector<vector<int>>new_grid(n, vector<int>(m)); for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { if(grid[i][j] > 0) { new_grid[i][j] = i * m + j; } else { new_grid[i][j] = -1; } } } apply(new_grid, pattern); for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { if(new_grid[i][j] == -1) { new_grid[i][j] = i * m + j; } } } // cout << "new_grid\n"; // for(int i = 0; i < n; i++) { // for(int j = 0; j < m; j++) { // cout << new_grid[i][j] << ' '; // } // cout << '\n'; // } new_grid = raise(new_grid, cyclic.size() / 4); /* cout << "new_grid raised\n"; for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { cout << new_grid[i][j] << ' '; } cout << '\n'; }*/ vector<vector<int>>my_grid(n, vector<int>(m)); for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { int x = new_grid[i][j] / m, y = new_grid[i][j] % m; my_grid[i][j] = grid[x][y]; } } grid = my_grid; // cout << "grid\n"; // print(grid); } for(int i = (int)cyclic.size() - cyclic.size() % 4; i < cyclic.size(); i++) apply(grid, cyclic[i]); print(grid); 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 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 | #include <iostream> #include <map> #include <vector> #include <stack> #include <algorithm> using namespace std; const long long mod = 1'000'000'007; vector<vector<int>> shift_up(vector<vector<int>>&v) { int n = v.size(), m = v[0].size(); vector<vector<int>>answer(n, vector<int>(m, -1)); for(int j = 0; j < m; j++) { stack<int>s; for(int i = 0; i < n; i++) { if(v[i][j] > -1) { s.push(v[i][j]); } } while(!s.empty()) { answer[(int)s.size() - 1][j] = s.top(); s.pop(); } } return answer; } vector<vector<int>> shift_down(vector<vector<int>>&v) { int n = v.size(), m = v[0].size(); vector<vector<int>>answer(n, vector<int>(m, -1)); for(int j = 0; j < m; j++) { stack<int>s; for(int i = n - 1; i >= 0; i--) { if(v[i][j] > -1) { s.push(v[i][j]); } } while(!s.empty()) { answer[n - (int)s.size()][j] = s.top(); s.pop(); } } return answer; } vector<vector<int>> shift_left(vector<vector<int>>&v) { int n = v.size(), m = v[0].size(); vector<vector<int>>answer(n, vector<int>(m, -1)); for(int i = 0; i < n; i++) { stack<int>s; for(int j = 0; j < m; j++) { if(v[i][j] > -1) { s.push(v[i][j]); } } while(!s.empty()) { answer[i][(int)s.size() - 1] = s.top(); s.pop(); } } return answer; } vector<vector<int>> shift_right(vector<vector<int>>&v) { int n = v.size(), m = v[0].size(); vector<vector<int>>answer(n, vector<int>(m, -1)); for(int i = 0; i < n; i++) { stack<int>s; for(int j = m - 1; j >= 0; j--) { if(v[i][j] > -1) { s.push(v[i][j]); } } while(!s.empty()) { answer[i][m - (int)s.size()] = s.top(); s.pop(); } } return answer; } void print(vector<vector<int>>&grid) { map<int, char>char_by_id = {{-1, '.'}, {1, 'B'}, {2, 'C'}}; for(vector<int>row : grid) { for(int x : row) { cout << char_by_id[x]; } cout << '\n'; } } void apply(vector<vector<int>>&grid, char c) { switch(c) { case 'L': grid = shift_left(grid); break; case 'P': grid = shift_right(grid); break; case 'G': grid = shift_up(grid); break; case 'D': grid = shift_down(grid); break; } } void apply(vector<vector<int>>&grid, string s) { for(char c : s) apply(grid, c); } vector<vector<int>>combine(vector<vector<int>>a, vector<vector<int>>b) { int n = a.size(), m = a[0].size(); vector<vector<int>>answer(n, vector<int>(m)); for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { int x = b[i][j] / m, y = b[i][j] % m; answer[i][j] = a[x][y]; } } return answer; } vector<vector<int>>raise(vector<vector<int>>&v, int k) { if(k == 1) return v; vector<vector<int>>answer = raise(v, k / 2); answer = combine(answer, answer); if(k % 2 == 1) answer = combine(answer, v); return answer; } int main() { ios_base::sync_with_stdio(0); int n, m; cin >> n >> m; vector<vector<int>>grid(n, vector<int>(m)); for(int i = 0; i < n; i++) { string s; cin >> s; for(int j = 0; j < m; j++) { switch(s[j]) { case '.': grid[i][j] = -1; break; case 'B': grid[i][j] = 1; break; case 'C': grid[i][j] = 2; break; } } } map<char, int>orientation = {{'L', 0}, {'P', 0}, {'G', 1}, {'D', 1}}; int k, i; cin >> k; string s; cin >> s; vector<char>last(2, -1); vector<int>cnt(2, 0); for(i = 0; i < k - 1; i++) { if(orientation[s[i]] != orientation[s[i + 1]]) { apply(grid, s[i]); apply(grid, s[i + 1]); last[orientation[s[i]]] = s[i]; last[orientation[s[i + 1]]] = s[i + 1]; cnt[0] = cnt[1] = 1; break; } } // cout << "grid\n"; // print(grid); // cout << '\n'; if(i == k - 1) { apply(grid, s[k - 1]); print(grid); return 0; } vector<char>cyclic; for(i += 2; i < k; i++) { while(i < k - 1 && orientation[s[i + 1]] == orientation[s[i]]) i++; if(last[orientation[s[i]]] == s[i]) { continue; } last[orientation[s[i]]] = s[i]; if(!cyclic.empty() && orientation[cyclic.back()] == orientation[s[i]]) { cyclic.pop_back(); if(cnt[orientation[s[i]]] == 1) { cyclic.push_back(s[i]); } else { cnt[orientation[s[i]]]--; } } else { cnt[orientation[s[i]]]++; cyclic.push_back(s[i]); } // cout << "cyclic = "; // for(char c : cyclic) // cout << c << ' '; // cout << '\n'; } /* cout << "cyclic = "; for(char c : cyclic) cout << c << ' '; cout << '\n';*/ if(cyclic.size() >= 4) { string pattern = ""; for(int i = 0; i < 4; i++) pattern += string(1, cyclic[i]); vector<vector<int>>new_grid(n, vector<int>(m)); for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { if(grid[i][j] > 0) { new_grid[i][j] = i * m + j; } else { new_grid[i][j] = -1; } } } apply(new_grid, pattern); for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { if(new_grid[i][j] == -1) { new_grid[i][j] = i * m + j; } } } // cout << "new_grid\n"; // for(int i = 0; i < n; i++) { // for(int j = 0; j < m; j++) { // cout << new_grid[i][j] << ' '; // } // cout << '\n'; // } new_grid = raise(new_grid, cyclic.size() / 4); /* cout << "new_grid raised\n"; for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { cout << new_grid[i][j] << ' '; } cout << '\n'; }*/ vector<vector<int>>my_grid(n, vector<int>(m)); for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { int x = new_grid[i][j] / m, y = new_grid[i][j] % m; my_grid[i][j] = grid[x][y]; } } grid = my_grid; // cout << "grid\n"; // print(grid); } for(int i = (int)cyclic.size() - cyclic.size() % 4; i < cyclic.size(); i++) apply(grid, cyclic[i]); print(grid); return 0; } |