import java.io.*;
import java.util.*;
public class competitive_contagion_18405 {
static class Block {
int value;
int y;
int x;
int sec;
Block(int value, int y, int x, int sec) {
this.value = value;
this.y = y;
this.x = x;
this.sec = sec;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
int[][] blocks = new int[N][N];
for (int i = 0; i < N; i++){
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++){
int value = Integer.parseInt(st.nextToken());
blocks[i][j] = value;
}
}
st = new StringTokenizer(br.readLine());
int S = Integer.parseInt(st.nextToken());
int X = Integer.parseInt(st.nextToken());
int Y = Integer.parseInt(st.nextToken());
boolean[][] visited = new boolean[N][N];
List<Block> queue = new ArrayList<>();
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (blocks[i][j] != 0) {
queue.add(new Block(blocks[i][j], i, j, 0));
visited[i][j] = true;
}
}
}
Collections.sort(queue, new Comparator<Block>() {
@Override
public int compare(Block b1, Block b2) {
return b1.value - b2.value;
}
});
int result = bfs(blocks, visited, queue, N, S, X, Y);
System.out.println(result);
}
public static int bfs(int[][] blocks, boolean[][] visited, List<Block> queue, int N, int S, int X, int Y) {
int[] dy = {-1, 1, 0, 0};
int[] dx = {0, 0, -1, 1};
while (!queue.isEmpty()) {
Block block = queue.remove(0);
int value = block.value;
int y = block.y;
int x = block.x;
int sec = block.sec;
if (sec == S) {
break;
}
for(int i = 0; i < 4; i++) {
int ny = dy[i] + y;
int nx = dx[i] + x;
if (ny >= 0 && ny < N && nx >= 0 && nx < N && !visited[ny][nx] && blocks[ny][nx] == 0) {
blocks[ny][nx] = value;
visited[ny][nx] = true;
queue.add(new Block(value, ny, nx, sec + 1));
}
}
}
return blocks[X-1][Y-1];
}
}
이 코드는 경쟁적 감염 문제를 해결하는 자바 코드입니다. 문제의 목표는 특정 시간(S) 후에 주어진 위치(X, Y)에 존재하는 바이러스의 종류를 알아내는 것입니다.
이 코드의 주요 로직은 다음과 같습니다:
먼저, 2차원 보드의 크기(N)와 바이러스의 종류(K)를 입력받습니다.
보드의 각 위치에 현재 존재하는 바이러스의 종류를 입력받습니다.
주어진 시간(S) 후에 알고자 하는 위치(X, Y)를 입력받습니다.
BFS를 사용하여 바이러스를 전파시킵니다. BFS를 시작하기 전에 초기에 존재하는 모든 바이러스를 큐에 추가하고, 각 바이러스가 보드에서 위치한 좌표와, 바이러스의 종류, 그리고 현재 시간(0초)을 저장합니다. 그 후에 바이러스의 종류를 기준으로 오름차순 정렬하여 작은 번호의 바이러스가 먼저 전파되도록 합니다.
BFS 를 진행하면서 큐에서 바이러스를 하나씩 꺼내고, 그 바이러스가 상하좌우로 전파되도록 합니다. 이때, 바이러스가 전파되는 곳이 보드를 벗어나지 않고, 이미 다른 바이러스에 의해 감염되지 않은 곳이어야 합니다. 바이러스가 전파되면 그 위치에 바이러스 종류를 저장하고, 그 위치를 방문했다는 것을 표시합니다. 그리고 현재 시간에 1을 더한 후 큐에 추가합니다.
만약 현재 시간이 주어진 시간(S)과 같아지면 BFS를 종료합니다.
마지막으로 주어진 위치(X, Y)에 존재하는 바이러스의 종류를 반환합니다.
이 알고리즘은 BFS를 이용하여 바이러스가 전파되는 과정을 시뮬레이션하며, 이를 통해 주어진 시간 후에 특정 위치에 어떤 바이러스가 존재하는지 알아냅니다.
const fs = require("fs");
const stdin = process.platform === "linux" ? fs.readFileSync("/dev/stdin").toString().trim() : fs.readFileSync("input.txt").toString().trim();
const input = stdin.split("\n");
let idx = 0;
const [N, K] = input[idx++].split(" ").map(Number);
const blocks = [];
for (let i = 0; i < N; i++) {
blocks.push(input[idx++].split(" ").map(Number));
}
const [S, X, Y] = input[idx++].split(" ").map(Number);
const visited = Array.from(Array(N), () => Array(N).fill(false));
const queue = [];
for (let i = 0; i < N; i++) {
for (let j = 0; j < N; j++) {
if (blocks[i][j] !== 0) {
queue.push([blocks[i][j], i, j, 0]);
visited[i][j] = true;
}
}
}
queue.sort((a, b) => a[0] - b[0]);
const result = bfs(blocks, visited, queue, S, N, X, Y);
console.log(result);
function bfs(blocks, visited, queue, S, N, X, Y) {
const dy = [-1, 1, 0, 0];
const dx = [0, 0, -1, 1];
while (queue.length > 0) {
const [value, y, x, sec] = queue.shift();
if (sec === S) {
break;
}
for (let d = 0; d < 4; d++) {
const ny = dy[d] + y;
const nx = dx[d] + x;
if (ny >= 0 && ny < N && nx >= 0 && nx < N && !visited[ny][nx] && blocks[ny][nx] === 0) {
blocks[ny][nx] = value;
visited[ny][nx] = true;
queue.push([value, ny, nx, sec + 1]);
}
}
}
return blocks[X - 1][Y - 1];
}
def bfs(blocks, visited, queue, S, N, X, Y):
dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]
while queue:
value, y, x, sec = queue.pop(0)
if sec == S:
break
for d in range(4):
ny = dy[d] + y
nx = dx[d] + x
if 0 <= ny < N and 0 <= nx < N and not visited[ny][nx] and blocks[ny][nx] == 0:
blocks[ny][nx] = value
visited[ny][nx] = True
queue.append((value, ny, nx, sec+1))
return blocks[X-1][Y-1]
N, K = map(int, input().split())
blocks = [list(map(int, input().split())) for _ in range(N)]
S, X, Y = map(int, input().split())
visited = [[False] * N for _ in range(N)]
queue = []
for i in range(N):
for j in range(N):
if blocks[i][j] != 0:
queue.append((blocks[i][j], i, j, 0))
visited[i][j] = True
queue.sort()
result = bfs(blocks, visited, queue, S, N, X, Y)
print(result)