백준[16927] 배열 돌리기 2

문제 설명

문제 링크

http://icpc.me/16927

16927번: 배열 돌리기 2

풀이

구현 문제다.

위의 그림과 같이 돌려야 하는 수들을 미리 덱에 저장해 두고, 덱의 맨 앞에 맨 뒤의 수를 집어넣는 것을 R번 하면 된다.

그런데 이때 R이 10^9으로 매우 크기 때문에 그냥 돌리면 시간 초과가 난다. 그렇기 때문에 덱의 크기만큼 돌리면 다시 덱이 초기의 상태랑 똑같아지기 때문에 R % (덱의 크기)만큼만 돌린다.

코드

#include <cstdio>
#include <deque>
#include <cstring>

using namespace std;

const int NN = 302;
int arr[NN][NN];
int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
bool visited[NN][NN];
deque<int> dq[NN];
int N, M, R;

bool posible(int r, int c, int d) {
    int nr = r + dir[d][0];
    int nc = c + dir[d][1];
    if (nr > N || nr < 1 || nc > M || nc < 1) return false;
    if (visited[nr][nc]) return false;
    return true;
}

int main() {
    scanf("%d %d %d", &N, &M, &R);
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++) scanf("%d", &arr[i][j]);
    
    int T = min(N, M) / 2;
    for (int i = 1; i <= T; i++) {
        int r = i, c = i, d = 0;
        while (1) {
            if (visited[r][c]) break;
            dq[i].push_back(arr[r][c]);
            visited[r][c] = true;
            if (!posible(r, c, d)) d++;
            if (d == 4) break;
            r = r + dir[d][0];
            c = c + dir[d][1];
        }
    }

    for (int i = 1; i <= T; i++) {
        int k = R % dq[i].size();
        while (k--) {
            dq[i].push_front(dq[i].back());
            dq[i].pop_back();
        }
    }

    memset(visited, 0, sizeof visited);
    for (int i = 1; i <= T; i++) {
        int r = i, c = i, d = 0, k = 0;
        while (1) {
            if (visited[r][c]) break;
            arr[r][c] = dq[i][k++];
            visited[r][c] = true;
            if (!posible(r, c, d)) d++;
            if (d == 4) break;
            r = r + dir[d][0];
            c = c + dir[d][1];
        }
    }

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) printf("%d ", arr[i][j]);
        printf("\n");
    }
}