名トマト
7229 ワード
名トマト
賢洙のトマト農場にはトマトを保管する大きな倉庫がある.
トマトは下図のように1つずつ四角い格子に入れて倉庫に保管しています.
倉庫に保管されているトマトの中には、熟しているものもあれば、まだ熟していないものもあります.1日保管した後、
熟したトマトに隣接して、熟していないトマトは熟したトマトの影響を受けて成熟します.
1つのトマトの隣接する場所は、左、右、前、後の4つの方向に位置するトマトを意味する.対角線方向にあるトマトには影響しません.
トマトは自分で成熟しないと仮定します.賢洙は倉庫に保管されているトマトが何日後に熟すか、最低日数を知りたいと思っている.
倉庫にはトマトのチェックボックスの大きさ、熟トマトと未熟トマトの情報が保管されています.
説明の入力
最初の行は、ボックスのサイズを表す2つの整数M,Nを与える.Mは箱の横欄数で、
Nは箱の縦格子数を表す.しかし,2≦M,N≦1000であった.
2行目から、1つの箱に保存されているトマトの情報が提供されます.
つまり、2行目からN行目まで、箱の中のトマトの情報が出てきます.
1本の線上で、箱の横線のトマトの状態はM個の整数である.
整数1は熟したトマトを表し、整数0は未熟のトマトを表し、整数-1はトマトを含まない格子を表す.
出力の説明
トマトがすべて熟成した最小日付を印刷します.
保存からすべてのトマトが熟成している場合は、0を出力する必要があります.
トマトがすべて成熟しない場合は、-1を出力します.
入力
6 4
0 0 -1 0 0 0
0 0 1 0 -1 0
0 0 -1 0 0 0
0 0 0 0 -1 1
しゅつりょく
4
誤った実装コード
static int answer = 0;
static int[] dx = {0,1,0,-1};
static int[] dy = {1,0,-1,0};
static int[][] box;
static Queue<Point> queue = new LinkedList<>();
static int m;
static int n;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
m = in.nextInt();
n = in.nextInt();
box = new int[n][m];
boolean check = true;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
box[i][j] = in.nextInt();
if(box[i][j]==0) check = false;
}
}
if (check) {
System.out.println(0);
return;
}
queue.offer(new Point(0,0));
bfs();
System.out.println(answer);
}
static void bfs(){
while (!queue.isEmpty()){
Point p = queue.poll();
if(box[p.x][p.y]==1){
for(int i=0;i<4;i++){
int nx = p.x + dx[i];
int ny = p.y + dy[i];
if(nx>=1 && nx<=n && ny>=1 && ny<=m && box[nx][ny]==0){
box[nx][ny] = 1;
queue.offer(new Point(nx,ny));
}
}
answer++;
}
else if(box[p.x][p.y]==-1) box[p.x][p.y]=1;
//박스가 빈 경우 토마토 있는걸로 생각
}
}
static class Point{
int x;
int y;
public Point(int x, int y){
this.x = x;
this.y = y;
}
}
前の質問迷路の最短通路と似ているので似たような答えを編んだのですが、条件の接近が間違っているようです.まず(0,0)bfsを呼び出し,1でなければ次へジャンプしなければならない.しかし、最初はwhileドアを回転させるように設定し、どの基準で次の座標に移るかを考えているうちに塞がれた.そしていっそ箱の中のトマトが熟している場合は、入力時にチェックさせますが、トマトが熟していない場合はどうやってチェックするか分かりません.
ベストアンサーを参考にした実装コード
static int[] dx = {0,1,0,-1};
static int[] dy = {1,0,-1,0};
static int[][] box;
static int[][] dis;
static Queue<Point> queue = new LinkedList<>();
static int m;
static int n;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
m = in.nextInt();
n = in.nextInt();
box = new int[n][m];
dis = new int[n][m];
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
box[i][j] = in.nextInt();
if(box[i][j]==1) queue.offer(new Point(i,j));
}
}
bfs();
boolean flag = true;
int answer = Integer.MIN_VALUE;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(box[i][j]==0) flag = false;
}
}
if(flag){
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
answer = Math.max(answer,dis[i][j]);
}
}
}
else{
answer = -1;
}
System.out.println(answer);
}
static void bfs(){
while (!queue.isEmpty()){
Point p = queue.poll();
for(int i=0;i<4;i++) {
int nx = p.x + dx[i];
int ny = p.y + dy[i];
if (nx >= 0 && nx < n && ny >= 0 && ny < m && box[nx][ny] == 0) {
box[nx][ny] = 1;
queue.offer(new Point(nx, ny));
dis[nx][ny] = dis[p.x][p.y] + 1;
}
}
}
}
static class Point{
int x;
int y;
public Point(int x, int y){
this.x = x;
this.y = y;
}
}
成熟した日付を格納する配列disを宣言します.最初に1と入力した場合は、すべてキューに入れます.1人から回るので.bfsを呼び出し、非1認知点付近の値を1に変換し、1に変換した点をキューに再入れます.
次にdisに前座標の値+1(所要時間)を加算する
bfsが終了したら、for文でドア全体を回って0があるかどうかをチェックします.ある場合は、すべて成熟することはできませんので、-1を返します.そうでない場合、disアレイの最大値は合計時間がかかるため、for文を切り替えるときに最大値が取り出されます.
よく感じることですが、手でコードするよりは頭で考える習慣をつけるべきです.今まであまり考えていなかったので、先に手を出しました.手を伸ばしたから...ああ...🧟♀️
Reference
この問題について(名トマト), 我々は、より多くの情報をここで見つけました https://velog.io/@yonii/토마토テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol