[ 백준 ][ 자바 ][ 7576 ] 토마토

토마토 문제 

어제 풀었던 문제의 2차원 버전이였다

이문제는 대각선 까지인가 싶었는데 아니었다.

일반적인 bfs문제였다. 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class tomatoPoint{
	int x;
	int y;
	tomatoPoint(int y, int x ){
		this.y = y;
		this.x = x;

	}
}
/*
 *
6 4
0 -1 0 0 0 0
-1 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1
 */
public class Main_backjoon_7576 {
	static Queue q = new LinkedList();
	static int[] dy = { 0, 0, 1, -1};
	static int[] dx = { 1, -1, 0, 0};
	static int MAP[][] = new int[1001][1001];
	static boolean visited[][] = new boolean[1001][1001];
	static int M; //가로
	static int N; //세로
	static int H; //높이
	static int CNT; //안익은 토마토 개수
	static int DAY; //흐른 시간
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		M = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());
			for(int i = 0 ; i < N; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				int idx = 0;
				while(st.hasMoreTokens()) {
					MAP[i][idx]= Integer.parseInt(st.nextToken());
					if( MAP[i][idx] == 1) {
						q.add(new tomatoPoint(i,idx));
						visited[i][idx] = true;
					}
					if( MAP[i][idx] == 0 ) {
						CNT+= 1;
					}
					idx +=1;
				}
			}
			ripening();
	}
	public static void ripening () {
		int ripe = 0;
		
		while(!q.isEmpty()) {
			
			int qsize = q.size();
			boolean move = false;
			for(int s = 0 ; s < qsize ; s++ ) {
				tomatoPoint tp = q.poll();
				for(int i = 0 ; i < 4; i++) {
					int xx = dx[i] + tp.x;
					int yy = dy[i] + tp.y; 
		
					if( yy >= 0 && yy < N && xx >=0 && xx < M) {
						if(MAP[yy][xx] != -1 && !visited[yy][xx] ) {
							visited[yy][xx] = true;
							q.add(new tomatoPoint(yy,xx));
							ripe += 1;
							move =true;
						}
					}
				}
	
			}
			if(move) DAY += 1;
		
		}
		//System.out.println(ripe);
		if( ripe == CNT) {
			System.out.println(DAY);
		}else {
			System.out.println(-1);
		}
		
	}
		
}