제출 #57337

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

rainbow

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

const int MAXN = 60;
const int dx[4] = {1,-1,0,0};
const int dy[4] = {0,0,1,-1};

int matriz[MAXN][MAXN],tamx,tamy;
int processado[MAXN][MAXN];
int lo_x,lo_y,hi_x,hi_y;

inline int valido(int x,int y){
	return x >= lo_x && y >= lo_y && x <= hi_x && y <= hi_y && matriz[x][y] != 1; 
}

void dfs(int x,int y){
	if(processado[x][y]) return;
	//printf("DFS %d %d\n",x,y);
	processado[x][y] = 1;
	for(int i = 0;i<4;i++){
		int nx = x + dx[i];
		int ny = y + dy[i];
		if(valido(nx,ny)) dfs(nx,ny);
	}
}

void init(int R, int C, int sr, int sc, int M, char *S) {
	tamx = R;tamy= C;
	matriz[sr][sc] = 1;
	for(int vez = 0;vez<M;vez++){
		if(S[vez] == 'N'){
			//printf("N\n");
			sr--;
		}
		else if(S[vez] == 'W'){
			//printf("W\n");
			sc--;
		}
		else if(S[vez] == 'S'){
			//printf("S\n");
			sr++;
		}
		else{
			//printf("E\n");
			sc++;
		}
		//printf("%d %d\n",sr,sc);
		matriz[sr][sc] = 1;
	}
	//for(int i = 1;i<=tamx;i++){
	//	for(int j = 1;j<=tamy;j++){
	//		printf("%d",matriz[i][j]);
	//	}
	//	printf("\n");
	//}
}

int colour(int ar, int ac, int br, int bc) {
    if(tamx <= 50 && tamy <= 50){
		memset(processado,0,sizeof(processado));
    		int total = 0;
    		lo_x = ar;lo_y = ac;
    		hi_x = br;hi_y = bc;
    		for(int i = ar;i<=br;i++){
    			for(int j = ac;j <= bc;j++){
    				if(matriz[i][j] == 1 || processado[i][j]) continue;
    				//printf("Componente nova\n");
    				dfs(i,j);
    				total++;
    			}
    		}
    		return total;
	}
	else return 0;
}

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