제출 #948317

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
948317		vjudge1	무지개나라 (APIO17_rainbow)	C++17	11 / 100	3039 ms	1048576 KiB

rainbow

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

int n , m , x , y ;
string s ;
map < int , map <int , int>> vis ;
map <char , int> f , a ;

void init(int R, int C, int sr, int sc, int M, char *S) {
	f['N'] = -1 ; f['S'] = 1 ;
	a['E'] = 1 ; a['W'] = -1 ;
	n = R ; m = C ; x = sr , y = sc ; s = S ;
	for ( int i = 0 ; i < M ; i ++ ) x += f[s[i]] , y += a[s[i]] , vis[x][y] = 2 ;
	vis[sr][sc] = 2 ;
}
int q , w ;
void dfs ( int i , int j ){
	vis[i][j] = 1 ;
	for ( int x = -1 ; x < 2 ; x ++ ){
		for ( int y = -1 ; y < 2 ; y ++ ){
			if ( x*y != 0 ) continue ;
			if ( x+i>=q && y+j >= w && x+i <= n && y+j <= m && vis[i+x][y+j] == 0 ) dfs(i+x,y+j) ;
		}
	}
}

int colour(int ar, int ac, int br, int bc) {
	int ans = 0 ;
	for ( int i = ar ; i <= br ; i ++ ){
		for ( int j = ac ; j <= bc ; j ++ ){
			if ( vis[i][j] == 1 ) vis[i][j] = 0 ;
		}
	}
	for ( int i = ar ; i <= br ; i ++ ){
		for ( int j = ac ; j <= bc ; j ++ ){
			if ( vis[i][j] == 0 ){
				n= br ; m = bc ;
				q = ar ; w = ac ;
				//cout << i << ' ' << j << endl; 
				ans ++ ; dfs(i,j) ;
			}
		}
	} 
    return ans ;
}

/*
static int R, C, M, Q;
static int sr, sc;
static char S[100000 + 5];

int main() {
    scanf("%d %d %d %d", &R, &C, &M, &Q);
    scanf("%d %d", &sr, &sc);
    if (M > 0) {
        scanf(" %s ", S);
    }

    init(R, C, sr, sc, M, S);

    int query;
    for (query = 0; query < Q; query++) {
        int ar, ac, br, bc;
        scanf("%d %d %d %d", &ar, &ac, &br, &bc);
        printf("%d\n", colour(ar, ac, br, bc));
    }

    return 0;
}
//*/

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