글 읽기 - 시간초과 모르겠습니다. 알려주세요ㅜㅜ

tmakdlf2770 3년 전 0

배양액 자리 조합 + 배양액 색깔뿌리기 조합 + 배양액 진행 bfs 했는데

시간초과가 생깁니다. ..

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;


public class B18809_Gaaaaaaaaaarden {
	static int map[][];
	static int G;
	static int R;
	static int N;
	static int M;
	static boolean Check[][];
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		G = sc.nextInt();
		R = sc.nextInt();
		map = new int[N][M];
		int ba = 0;
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				map[i][j]=sc.nextInt();
				if(map[i][j]==2) {
					ba++;
				}
			}
		}
		Pair arr[]=new Pair[ba];
		boolean[] visited = new boolean[ba];
		int a=0;
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(map[i][j]==2) {
					arr[a]=new Pair(i, j);
					a++;
				}
			}
		}
		max=0;
		combination(arr, visited, 0, ba, G+R);
		System.out.println(max);




	}
	static void combination(Pair[] arr, boolean[] visited, int start, int n, int r) {
		if(r == 0) {
			comb(arr, visited, n);
			return;
		} 

		for(int i=start; i<n; i++) {
			visited[i] = true;
			combination(arr, visited, i + 1, n, r - 1);
			visited[i] = false;
		}
	}
	static void comb(Pair[] arr, boolean[] visited, int n) {
		Pair[] arr1 = new Pair[G+R];
		int a=0;
		boolean[] visited1 = new boolean[G+R];
		for (int i = 0; i < n; i++) {
			if (visited[i] == true) {
				int x=arr[i].x;
				int y=arr[i].y;
				
				arr1[a]=new Pair(x, y);
				a++;
			}
		}
		
		combination1(arr1, visited1, 0, G+R, G );

	}
	static void combination1(Pair[] arr, boolean[] visited, int start, int n, int r) {
		if(r == 0) {
			comb1(arr, visited, n);
			return;
		} 

		for(int i=start; i<n; i++) {
			visited[i] = true;
			combination1(arr, visited, i + 1, n, r - 1);
			visited[i] = false;
		}
	}
	static void comb1(Pair[] arr, boolean[] visited, int n) {
		Queue<Pair1> q = new LinkedList<>();
		Check = new boolean[N][M];
		for (int i = 0; i < n; i++) {
			if (visited[i] == true) {
				int x = arr[i].x;
				int y = arr[i].y;
				q.add(new Pair1(x,y,4));
				Check[x][y]=true;

			}else {
				int x = arr[i].x;
				int y = arr[i].y;
				q.add(new Pair1(x, y, 5));
				Check[x][y]=true;
			}
		}
		int count=0;
		int map1[][] = new int[N][M];
		boolean[][] flower = new boolean[N][M];
		while(!q.isEmpty()) {
			
			boolean[][] time = new boolean[N][M];
			
			int size = q.size();
			for(int j=0; j<size; j++) {
				Pair1 p = q.poll();
				if(flower[p.x][p.y])continue;
				for(int i=0;i<4;i++) {
					int tx = p.x+dir[i][0];
					int ty = p.y+dir[i][1];
					if(tx<0 || ty<0 || tx>=N || ty>=M) continue;
					if(map[tx][ty]==0)continue;
					if(flower[tx][ty])continue;
					if(time[tx][ty]&&p.color!=map1[tx][ty]) {
						Check[tx][ty]=true;
						flower[tx][ty]=true;
						count++;
					}
					if(Check[tx][ty])continue;
					if(map[tx][ty]==1||map[tx][ty]==2) {
						q.add(new Pair1(tx, ty, p.color));
						time[tx][ty]=true;
						Check[tx][ty]=true;
						map1[tx][ty]=p.color;
						continue;
					}
					

				}
			}
		}

		max = Math.max(max, count);
	}
	static int max;
	static int[][] dir = {{-1,0},{0,-1},{1,0},{0,1}};

	static class Pair{
		private int y,x;

		Pair(int x, int y){
			this.y = y;
			this.x = x;
		}
	}
	static class Pair1{
		private int y,x,color;

		Pair1(int x, int y,int color){
			this.y = y;
			this.x = x;
			this.color = color;
		}
	}


}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과 모르겠습니다. 알려주세요ㅜㅜ

tmakdlf2770 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말