Submission #57256

#	Time	Username	Problem	Language	Result	Execution time	Memory
57256		gabrielsimoes	무지개나라 (APIO17_rainbow)	C++17	11 / 100	3029 ms	1844 KiB

rainbow

#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;

const int MAX = 55;

int dr[] = {-1, 0, 1, 0};
int dc[] = {0, 1, 0, -1};

int R, C;
bitset<MAX> land[MAX];

void init(int _R, int _C, int sr, int sc, int M, char *S) {
    R = _R; C = _C;
    for (int r = 1; r <= R; r++)
        for (int c = 1; c <= C; c++)
            land[r][c] = true;

    land[sr][sc] = false;
    for (int i = 0; i < M; i++) {
        int d = 0;
        switch(S[i]) {
            case 'N': d = 0; break;
            case 'E': d = 1; break;
            case 'S': d = 2; break;
            case 'W': d = 3; break;
        }
        sr += dr[d];
        sc += dc[d];
        land[sr][sc] = false;
    }
}

int color[MAX][MAX], _color = 0;
void dfs_1(int r, int c, int ar, int ac, int br, int bc) {
    for (int d = 0; d < 4; d++) {
        int nr = r + dr[d], nc = c + dc[d];
        if (r >= ar && r <= br && c >= ac && c <= bc && land[nr][nc] && color[nr][nc] == 0) {
            color[nr][nc] = color[r][c];
            dfs_1(nr, nc, ar, ac, br, bc);
        }
    }
}


int colour(int ar, int ac, int br, int bc) {
    for (int r = ar; r <= br; r++)
        for (int c = ac; c <= bc; c++)
            color[r][c] = 0;
    _color= 0;

    for (int r = ar; r <= br; r++) {
        for (int c = ac; c <= bc; c++) {
            if (land[r][c] && color[r][c] == 0) {
                color[r][c] = ++_color;
                dfs_1(r, c, ar, ac, br, bc);
            }
        }
    }

    return _color;
}

• Subtask 1: 11 / 11
• Subtask 2: 0 / 12
• Subtask 3: 0 / 24
• Subtask 4: 0 / 27
• Subtask 5: 0 / 26