JOI 春合宿 2012-day2 Rotate
問題文 : 回転
解法 :
リストを使う. 右と下にいけるリストがあれば, 90 * n (0 ≦ n < 4) 度ごとに回転した盤面の境界のO(N) 個のマスのポインタをペタペタ張り替えることでO(QN + N^2) でこの問題を解く事が出来る.
ローカルでは最大ケースに2.6sec かかり, AtCoder でも10 点分しか点数が得れないので, O(QN^2) 書いたのと同じ扱いで涙しかない...
コード :
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; struct Node { Node *next, *down; char val; }; int N, Q; char str[1024][1024]; Node board[4][1024][1024]; inline void init(int x) { for (int i = 0; i < N; i++){ Node *tmp = &board[x][i][0]; for (int j = 0; j < N; j++){ tmp->val = str[i][j]; tmp->next = &board[x][i][j + 1]; tmp->down = &board[x][i + 1][j]; tmp = tmp->next; } } } char tmp[1024][1024]; inline void rotate() { for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) tmp[i][j] = str[j][N - i - 1]; memcpy(str, tmp, sizeof(tmp)); } inline void rotate_simple(int sy, int sx, int S) { Node *left[4], *right[4], *left2[4], *right2[4]; Node *top[4], *bottom[4], *top2[4], *bottom2[4]; for (int i = 0; i < 4; i++){ left[i] = &board[i][sy][0], right[i] = &board[i][sy][0]; left2[i] = &board[i][sy][0], right2[i] = &board[i][sy][0]; top[i] = &board[i][0][sx], bottom[i] = &board[i][0][sx]; top2[i] = &board[i][0][sx], bottom2[i] = &board[i][0][sx]; for (int j = 0; j < max(sx, sy) + S; j++){ if (j < sx - 1) left[i] = left[i]->next; if (j < sx) left2[i] = left2[i]->next; if (j < sx + S - 1) right[i] = right[i]->next; if (j < sx + S) right2[i] = right2[i]->next; if (j < sy - 1) top[i] = top[i]->down; if (j < sy) top2[i] = top2[i]->down; if (j < sy + S - 1) bottom[i] = bottom[i]->down; if (j < sy + S) bottom2[i] = bottom2[i]->down; } int nexty = (N - 2) - (sx + S - 1) + 1; int nextx = sy; sy = nexty; sx = nextx; } for (int i = 0; i < 4; i++){ for (int j = 0; j < S; j++){ int i2 = (i + 1) % 4; left[i]->next = left2[i2]; left[i] = left[i]->down; left2[i2] = left2[i2]->down; right[i2]->next = right2[i]; right[i2] = right[i2]->down; right2[i] = right2[i]->down; top[i]->down = top2[i2]; top[i] = top[i]->next; top2[i2] = top2[i2]->next; bottom[i2]->down = bottom2[i]; bottom[i2] = bottom[i2]->next; bottom2[i] = bottom2[i]->next; } } } int main() { scanf("%d %d", &N, &Q); for (int i = 0; i < N; i++){ scanf("%s", &str[i + 1][1]); } N += 2; for (int i = 0; i < 4; i++){ init(i); rotate(); } for (int i = 0; i < Q; i++){ int I, J, K; scanf("%d %d %d", &I, &J, &K); rotate_simple(I, J, K); } for (int i = 1; i < N - 1; i++){ Node *tmp = &board[0][i][0]; for (int j = 0; j < N - 2; j++){ tmp = tmp->next; printf("%c", tmp->val); } printf("\n"); } return (0); }