白駿-トマト[7576]
18661 ワード
質問する
チョルスのトマト農場にはトマトを保管する大きな倉庫がある.トマトは下図のように1つずつ四角い格子に入れて倉庫に保管しています.
倉庫に保管されているトマトの中には、熟しているものもあれば、まだ熟していないものもあります.1日保管した後、熟したトマトに隣接する未熟のトマトは、熟したトマトの影響を受けて成熟する.1つのトマトの隣接する場所は、左、右、前、後の4つの方向に位置するトマトを意味する.対角線方向に影響を与えないトマトは、トマトが自分で成熟しないと仮定します.哲洙は倉庫に保管されているトマトが何日で熟れるか、最低日数を知りたいと思っている.
倉庫にトマトのチェックボックスの大きさ、熟したトマトと未熟なトマトの情報を保管している場合、数日後には、トマトが熟しているかどうか、最低日数を求めるプログラムを作成します.しかし、箱のいくつかの格にはトマトが入っていないかもしれません.
入力
最初の行は、ボックスのサイズを表す2つの整数M,Nを与える.Mは箱の横格子数,Nは箱の縦格子数を表す.しかし,2≦M,N≦1000であった.2行目から、1つの箱に保存されているトマトの情報が提供されます.つまり、2行目からN行目まで、箱の中のトマトの情報が出てきます.1本の線上で、箱の横線のトマトの状態はM個の整数である.整数1は熟したトマトを表し、整数0は未熟のトマトを表し、整数-1はトマトを含まない格子を表す.
トマトが1つ以上ある場合にのみ入力します.
しゅつりょく
トマトがすべて熟成した最小日付を印刷します.保存からすべてのトマトが熟成している場合は0を、トマトが熟成していない場合は-1を出力します.
に答える
この問題はbfsで解決できる.迷宮探索で最短経路を求める方式と同様に,以前の値に+1を加えればよい.
熟したトマト(1と表記されている点)をQに早めに入れ、Qが願い事をするまで上下左右を探索し、熟しているトマトがあるかどうかは、以前の値+1でOKです.
範囲外またはまだ完熟していないトマトでなければ(0でなければ)、スキップして行うことができます.
最終的にarr配列に0がある場合は-1を出力し、そうでない場合は最大値-1を出力するだけです.(-1の理由は1日目からではなく2日目からです.)
ソース import java.util.*;
class Node {
private int x;
private int y;
public Node(int x, int y) {
this.x = x;
this.y = y;
}
public int getX() {
return x;
}
public int getY() {
return y;
}
}
public class Main {
public static int n, m;
public static int[][] arr;
public static int[] dx = { -1, 1, 0, 0 };
public static int[] dy = { 0, 0, -1, 1 };
public static void bfs() {
Queue<Node> q = new LinkedList<Node>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (arr[i][j] == 1) {
q.offer(new Node(i, j));
}
}
}
while (!q.isEmpty()) {
Node node = q.poll();
int x = node.getX();
int y = node.getY();
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
continue;
}
if (arr[nx][ny] != 0) {
continue;
}
arr[nx][ny] = arr[x][y] + 1;
q.offer(new Node(nx, ny));
}
}
int max = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (arr[i][j] == 0) {
System.out.println(-1);
return;
}
max = Math.max(max, arr[i][j]);
}
}
System.out.println(max - 1);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
m = sc.nextInt();
n = sc.nextInt();
arr = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
arr[i][j] = sc.nextInt();
}
}
bfs();
}
}
Reference
この問題について(白駿-トマト[7576]), 我々は、より多くの情報をここで見つけました
https://velog.io/@minuk1236/백준-토마토-7576
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
最初の行は、ボックスのサイズを表す2つの整数M,Nを与える.Mは箱の横格子数,Nは箱の縦格子数を表す.しかし,2≦M,N≦1000であった.2行目から、1つの箱に保存されているトマトの情報が提供されます.つまり、2行目からN行目まで、箱の中のトマトの情報が出てきます.1本の線上で、箱の横線のトマトの状態はM個の整数である.整数1は熟したトマトを表し、整数0は未熟のトマトを表し、整数-1はトマトを含まない格子を表す.
トマトが1つ以上ある場合にのみ入力します.
しゅつりょく
トマトがすべて熟成した最小日付を印刷します.保存からすべてのトマトが熟成している場合は0を、トマトが熟成していない場合は-1を出力します.
に答える
この問題はbfsで解決できる.迷宮探索で最短経路を求める方式と同様に,以前の値に+1を加えればよい.
熟したトマト(1と表記されている点)をQに早めに入れ、Qが願い事をするまで上下左右を探索し、熟しているトマトがあるかどうかは、以前の値+1でOKです.
範囲外またはまだ完熟していないトマトでなければ(0でなければ)、スキップして行うことができます.
最終的にarr配列に0がある場合は-1を出力し、そうでない場合は最大値-1を出力するだけです.(-1の理由は1日目からではなく2日目からです.)
ソース import java.util.*;
class Node {
private int x;
private int y;
public Node(int x, int y) {
this.x = x;
this.y = y;
}
public int getX() {
return x;
}
public int getY() {
return y;
}
}
public class Main {
public static int n, m;
public static int[][] arr;
public static int[] dx = { -1, 1, 0, 0 };
public static int[] dy = { 0, 0, -1, 1 };
public static void bfs() {
Queue<Node> q = new LinkedList<Node>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (arr[i][j] == 1) {
q.offer(new Node(i, j));
}
}
}
while (!q.isEmpty()) {
Node node = q.poll();
int x = node.getX();
int y = node.getY();
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
continue;
}
if (arr[nx][ny] != 0) {
continue;
}
arr[nx][ny] = arr[x][y] + 1;
q.offer(new Node(nx, ny));
}
}
int max = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (arr[i][j] == 0) {
System.out.println(-1);
return;
}
max = Math.max(max, arr[i][j]);
}
}
System.out.println(max - 1);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
m = sc.nextInt();
n = sc.nextInt();
arr = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
arr[i][j] = sc.nextInt();
}
}
bfs();
}
}
Reference
この問題について(白駿-トマト[7576]), 我々は、より多くの情報をここで見つけました
https://velog.io/@minuk1236/백준-토마토-7576
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
この問題はbfsで解決できる.迷宮探索で最短経路を求める方式と同様に,以前の値に+1を加えればよい.
熟したトマト(1と表記されている点)をQに早めに入れ、Qが願い事をするまで上下左右を探索し、熟しているトマトがあるかどうかは、以前の値+1でOKです.
範囲外またはまだ完熟していないトマトでなければ(0でなければ)、スキップして行うことができます.
最終的にarr配列に0がある場合は-1を出力し、そうでない場合は最大値-1を出力するだけです.(-1の理由は1日目からではなく2日目からです.)
ソース import java.util.*;
class Node {
private int x;
private int y;
public Node(int x, int y) {
this.x = x;
this.y = y;
}
public int getX() {
return x;
}
public int getY() {
return y;
}
}
public class Main {
public static int n, m;
public static int[][] arr;
public static int[] dx = { -1, 1, 0, 0 };
public static int[] dy = { 0, 0, -1, 1 };
public static void bfs() {
Queue<Node> q = new LinkedList<Node>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (arr[i][j] == 1) {
q.offer(new Node(i, j));
}
}
}
while (!q.isEmpty()) {
Node node = q.poll();
int x = node.getX();
int y = node.getY();
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
continue;
}
if (arr[nx][ny] != 0) {
continue;
}
arr[nx][ny] = arr[x][y] + 1;
q.offer(new Node(nx, ny));
}
}
int max = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (arr[i][j] == 0) {
System.out.println(-1);
return;
}
max = Math.max(max, arr[i][j]);
}
}
System.out.println(max - 1);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
m = sc.nextInt();
n = sc.nextInt();
arr = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
arr[i][j] = sc.nextInt();
}
}
bfs();
}
}
Reference
この問題について(白駿-トマト[7576]), 我々は、より多くの情報をここで見つけました
https://velog.io/@minuk1236/백준-토마토-7576
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
import java.util.*;
class Node {
private int x;
private int y;
public Node(int x, int y) {
this.x = x;
this.y = y;
}
public int getX() {
return x;
}
public int getY() {
return y;
}
}
public class Main {
public static int n, m;
public static int[][] arr;
public static int[] dx = { -1, 1, 0, 0 };
public static int[] dy = { 0, 0, -1, 1 };
public static void bfs() {
Queue<Node> q = new LinkedList<Node>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (arr[i][j] == 1) {
q.offer(new Node(i, j));
}
}
}
while (!q.isEmpty()) {
Node node = q.poll();
int x = node.getX();
int y = node.getY();
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
continue;
}
if (arr[nx][ny] != 0) {
continue;
}
arr[nx][ny] = arr[x][y] + 1;
q.offer(new Node(nx, ny));
}
}
int max = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (arr[i][j] == 0) {
System.out.println(-1);
return;
}
max = Math.max(max, arr[i][j]);
}
}
System.out.println(max - 1);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
m = sc.nextInt();
n = sc.nextInt();
arr = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
arr[i][j] = sc.nextInt();
}
}
bfs();
}
}
Reference
この問題について(白駿-トマト[7576]), 我々は、より多くの情報をここで見つけました https://velog.io/@minuk1236/백준-토마토-7576テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol