BJ 16236サメ
25750 ワード
https://www.acmicpc.net/problem/16236
NxNサイズの地図で、中には魚とサメの位置があります.
サメは自分より小さい魚しか食べられず、サメの大きさは食べる魚の数とともに増加します.
問題はサメが魚を食べる時間が必要だということです.
魚をリストに並べて管理し、BFSで実現します.
NxNサイズの地図で、中には魚とサメの位置があります.
サメは自分より小さい魚しか食べられず、サメの大きさは食べる魚の数とともに増加します.
問題はサメが魚を食べる時間が必要だということです.
魚をリストに並べて管理し、BFSで実現します.
package day0223;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Collections;
import java.util.LinkedList;
import java.util.StringTokenizer;
public class Shark {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static StringTokenizer st;
static int[][] map;
static int N, x, y, sharkSize = 2, time = 0, numofEat = 0;
static int[][] dir = {{1, 0},{0, -1},{0,1},{-1,0}};
public static class Fish implements Comparable<Fish> {
int x, y, dist;
public Fish(int x, int y, int dist) {
super();
this.x = x;
this.y = y;
this.dist = dist;
}
@Override
public int compareTo(Fish o) {
return this.dist == o.dist ? (this.x == o.x ? (this.y - o.y) : this.x - o.x) : this.dist - o.dist;
}
}
public static void main(String[] args) throws IOException {
N = Integer.parseInt(br.readLine());
int tmp;
map = new int[N][N];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine(), " ");
for (int j = 0; j < N; j++) {
tmp = Integer.parseInt(st.nextToken());
if (tmp == 9) {
x = i;
y = j;
} else {
map[i][j] = tmp;
}
}
}
LinkedList<Fish> q = new LinkedList<Fish>();
boolean[][] visited = new boolean[N][N];
visited[x][y] = true;
q.add(new Fish(x, y, 0));
while(!q.isEmpty()) {
Fish cur = q.poll();
if(map[cur.x][cur.y] != 0 && map[cur.x][cur.y] < sharkSize) {
numofEat++;
if(numofEat == sharkSize) {
sharkSize++;
numofEat = 0;
}
time += cur.dist;
x = cur.x;
y = cur.y;
map[x][y] = 0;
visited = new boolean[N][N];
visited[x][y] = true;
q.clear();
q.add(new Fish(cur.x, cur.y, 0));
Collections.sort(q);
continue;
}
for(int d = 0; d < 4; d++) {
int mX = cur.x + dir[d][0];
int mY = cur.y + dir[d][1];
// 이동할 수 없는 곳 걸러내기.
if(mX >= N || mX < 0 || mY >= N || mY < 0) {
continue;
}else if(visited[mX][mY]) {
continue;
}else if(sharkSize < map[mX][mY]) {
continue;
}
q.add(new Fish(mX, mY, cur.dist + 1));
Collections.sort(q);
visited[mX][mY] = true;
}
}
bw.append(Integer.toString(time));
bw.flush();
}
}
Reference
この問題について(BJ 16236サメ), 我々は、より多くの情報をここで見つけました https://velog.io/@mraz0210/BJ16236-아기-상어テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol