제출 #1203802

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1203802		jj_master	무지개나라 (APIO17_rainbow)	C++20	11 / 100	3093 ms	12524 KiB

rainbow

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

const int N = 1005;
bool riv[N][N], vis[N][N];

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

bool in(int r, int c, int r1, int c1, int r2, int c2) {
    return r >= r1 && r <= r2 && c >= c1 && c <= c2;
}

void dfs(int r, int c, int r1, int c1, int r2, int c2) {
    vis[r][c] = 1;
    for (int d = 0; d < 4; d++) {
        int nr = r + dr[d];
        int nc = c + dc[d];
        if (in(nr, nc, r1, c1, r2, c2) && !riv[nr][nc] && !vis[nr][nc]) {
            dfs(nr, nc, r1, c1, r2, c2);
        }
    }
}

void init(int r, int c, int sr, int sc, int m, char* s) {
    memset(riv, 0, sizeof(riv));
    int x = sr, y = sc;
    riv[x][y] = 1;
    for (int i = 0; i < m; ++i) {
        if (s[i] == 'N') --x;
        else if (s[i] == 'S') ++x;
        else if (s[i] == 'E') ++y;
        else if (s[i] == 'W') --y;
        riv[x][y] = 1;
    }
}

int colour(int r1, int c1, int r2, int c2) {
    for (int i = r1; i <= r2; ++i)
        for (int j = c1; j <= c2; ++j)
            vis[i][j] = 0;

    int count = 0;
    for (int i = r1; i <= r2; ++i)
        for (int j = c1; j <= c2; ++j)
            if (!riv[i][j] && !vis[i][j]) {
                dfs(i, j, r1, c1, r2, c2);
                count++;
            }

    return count;
}

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