https://www.acmicpc.net/problem/7569
7569번: 토마토
첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100,
www.acmicpc.net
분류 : BFS
더보기
import java.io.*;
import java.math.*;
import java.util.*;
class MyScanner {
BufferedReader br;
StringTokenizer st;
public MyScanner() {
br = new BufferedReader(new InputStreamReader(System.in));
}
String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong() {
return Long.parseLong(next());
}
double nextDouble() {
return Double.parseDouble(next());
}
char nextChar() {
return next().charAt(0);
}
}
public class Main
{
public static PrintWriter out;
static int R,C,H;
static boolean[][][] visited;
static int[][][] farm;
static int[] dx = {0,0,0,0,-1,1};
static int[] dy = {0,0,-1,1,0,0};
static int[] dz = {-1,1,0,0,0,0};
static Queue<Point> q = new LinkedList<Point>();
public static void main(String[] args) throws IOException
{
MyScanner sc = new MyScanner();
out = new PrintWriter(new BufferedOutputStream(System.out));
R = sc.nextInt();
C = sc.nextInt();
H = sc.nextInt();
farm= new int[H][C][R];
visited = new boolean[H][C][R];
for(int h=0;h<H;h++)
{
for(int c =0;c<C;c++)
{
for(int r=0;r<R;r++)
{
farm[h][c][r]=sc.nextInt();
if(farm[h][c][r]==1)
{
q.offer(new Point(h,c,r));
}
}
}
}
bfs();
boolean check =true;
int max =-1;
loop1: for(int h=0;h<H;h++)
{
for(int c =0;c<C;c++)
{
for(int r=0;r<R;r++)
{
max = Math.max(max, farm[h][c][r]);
if(farm[h][c][r]==0){
check = false;
break loop1;
}
}
}
}
if(!check){
out.println(-1);
}
else{
out.print(max-1);
}
out.flush();
}
private static void bfs() {
while(!q.isEmpty())
{
int size =q.size();
for(int sz =0; sz<size;sz++)
{
Point p = q.poll();
int h = p.h;
int c = p.c;
int r = p.r;
for(int dr = 0;dr<6;dr++)
{
int ch = h+dz[dr];
int cr = r+dx[dr];
int cc = c+dy[dr];
if(ch>=0 && cr>=0 && cc>=0 && cr<R && cc<C && ch<H)
if(farm[ch][cc][cr]==0 && visited[ch][cc][cr]==false){
farm[ch][cc][cr]=farm[h][c][r]+1;
visited[ch][cc][cr] = true;
q.offer(new Point(ch,cc,cr));
}
}
}
}
}
}
class Point{
int h;
int c;
int r;
Point(int h,int c , int r){
this.h=h;
this.c=c;
this.r=r;
}
}
https://www.acmicpc.net/problem/7576 -> 토마토 문제와 비슷하지만 층 개념이 생겼다는 점이 다르다.
그래서 for문을 돌릴 때 높이 -> 세로 -> 가로 식으로 진행되는 것만 조심하면 되지 않을까 싶다.
'PS' 카테고리의 다른 글
[BOJ]5427번 : 불 (0) | 2017.03.31 |
---|---|
[BOJ]4179번 : Fire! (0) | 2017.03.31 |
[BOJ]10974번 : 모든 순열 (0) | 2017.03.29 |
[BOJ]11657번 : 타임 머신 (0) | 2017.03.28 |
[BOJ]4195번 : 친구 네트워크 (0) | 2017.03.25 |