読者です 読者をやめる 読者になる 読者になる

Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

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);
}