R줄 C칸짜리 종이에 물감 방울이 몇 개 떨어진다.
'.'은 빈칸, '#'은 물감이 스미지 않는 칸, 영어 대문자는 그 글자 색의 물감 방울이 떨어질 칸이다.
글자마다 방울이 떨어지는 시각(분)이 주어진다.
방울이 떨어지기 전에는 그 칸도 빈칸으로 친다.
두 칸은 위·아래·왼쪽·오른쪽으로 맞닿을 때 이웃이다.
0분부터 1분씩, 매분 다음 두 단계를 차례로 한다.
1단계(번지기): 직전 분이 끝났을 때 글자가 있는 이웃이 하나라도 있는 빈칸은 모두, 직전 분이 끝났을 때의 상태만 보고 한꺼번에 바뀐다.
그 빈칸의 이웃 가운데 가장 많이 나온 글자로 바뀌고, 가장 많이 나온 글자가 둘 이상이면 '*'로 바뀐다.
'*' 칸과 '#' 칸은 글자로 치지 않으며, '*' 칸은 다시 바뀌지 않는다.
2단계(떨어지기): 이번 분에 떨어지는 방울은 자기 칸이 아직 빈칸일 때만 그 칸을 자기 글자로 만든다.
자기 칸이 이미 다른 글자나 '*'가 되었으면 그 방울은 없던 일이 된다.
0분에는 직전 분이 없으므로 떨어지기만 한다.
한 번 글자가 된 칸은 다시 바뀌지 않는다.
더 바뀔 칸도, 떨어질 방울도 없을 때 종이의 모습을 출력하라.
떨어진 방울과 번진 칸은 그 글자로, 비긴 칸은 '*'로, 끝까지 빈칸인 칸은 '.'으로, '#'은 그대로 출력한다.
입력
첫 줄에 R과 C, 다음 R줄에 '.', '#', 영어 대문자로 된 길이 C인 문자열, 다음 줄에 방울 수 K, 다음 K줄에 줄마다 글자 L과 떨어지는 시각 t가 빈칸으로 나뉘어 주어진다. 1 ≤ R, C ≤ 50, 0 ≤ K ≤ 26, 0 ≤ t ≤ 10,000. 지도에 나오는 대문자는 서로 다르고, K줄의 글자는 지도에 나오는 대문자와 정확히 같다(차례는 아무렇게나 온다).
출력
R줄, 줄마다 길이 C인 문자열(마지막 종이 모습)
예시 1 · stdin
3 5
A...B
.....
..#..
2
A 0
B 0
stdout
AA*BB
AA*BB
AA#BB
예시 2 · stdin
4 4
.A#.
....
B...
...C
3
A 3
B 0
C 2
stdout
BB#B
BBBB
BBB*
BBBC
main.py
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
여러 곳에서 동시에 퍼지는 일은 너비 우선 탐색(BFS)을 한 겹씩 돌려요. 큐에 직전 분에 새로 칠해진 칸(한 겹)만 두고, 그 이웃 빈칸을 이번 분의 후보로 모은 다음, 후보마다 이웃 글자 수를 세어 모두 정한 뒤에 한꺼번에 칠해요. 직전 분에 칠해진 칸만 큐에 있으면 되는 까닭: 더 오래전에 칠해진 칸의 이웃 빈칸은 이미 그다음 분에 바뀌었기 때문이에요. 가장 흔한 함정은 보통의 BFS처럼 큐에서 꺼내는 대로 이웃을 바로 칠하는 것이에요 — 그러면 같은 분에 도착한 다른 색과 겨루지도 못하고 먼저 꺼낸 쪽이 차지해서, 비김('*')과 다수결이 사라져요. 다른 함정: 비겼을 때 알파벳이 빠른 글자에게 주기, '*'를 큐에 넣어 '*'가 번지게 하기, 방울을 번지기보다 먼저 떨어뜨리기(그러면 물감이 번져 오는 바로 그 분에 떨어지는 방울이 덮이지 않고 살아남아요). 방울이 하나도 없는 동안은 1분씩 세지 말고 다음 방울 시각으로 건너뛰면 돼요(10,000분을 그냥 세어도 느리진 않아요). 같은 분에 한 칸을 두 번 후보로 넣지 않으려면 '이번 분에 넣었음' 표시를 분 번호로 남겨 두면 매분 지울 필요가 없어요. 표 다루는 법: Python은 list(row)로 줄을 글자 목록으로 바꾸고 dict로 표를 세요. Java는 char[][]와 int[26] 표, 시작 시각 정렬은 Comparator.comparingInt(Start::t). C#은 char[][], new int[r, c](직사각형 배열), 이름 붙은 튜플 목록과 OrderBy. C++은 std::vector<std::string>과 std::array<int, 26>, std::max_element·std::count로 가장 많은 글자와 비김을 찾아요. C는 고정 크기 배열과 qsort(비교 함수가 음수·0·양수를 돌려줘요). JavaScript·TypeScript는 Map으로 세고 Math.max(...votes.values()). 크레이콘은 지도를 한 글자 문자열의 2차원 목록으로 두고 사전()으로 세며, votes.열쇠목록을 돌아 가장 많은 수와 그 수가 몇 번 나왔는지 봐요. 시작 시각 정렬은 starts.정렬(시각순)처럼 비교 함수를 넘기고, 줄은 row.잇기("")로 이어 써요.
Pythonmain.py · 56 줄
import sysdata = sys.stdin.read().split("\n")r, c = map(int, data[0].split())grid = [list(data[1 + y].strip()) for y in range(r)]k = int(data[1 + r])starts = [] # (시작 분, 글자, y, x)where = {grid[y][x]: (y, x) for y in range(r) for x in range(c) if grid[y][x].isupper()}for line in data[2 + r:2 + r + k]: letter, t = line.split() starts.append((int(t), letter, *where[letter])) grid[where[letter][0]][where[letter][1]] = "." # 시작하기 전에는 빈칸이다starts.sort()STEPS = ((-1, 0), (1, 0), (0, -1), (0, 1))frontier = [] # 직전 분에 새로 글자를 얻은 칸들(너비 우선 탐색의 한 겹)nxt = 0 # 아직 시작하지 않은 첫 출발점minute = 0while frontier or nxt < len(starts): if not frontier: minute = max(minute, starts[nxt][0]) # 퍼질 것이 없으면 다음 출발 시각으로 건너뛴다 # 1) 퍼지기: 직전 분 상태로 모든 빈칸을 한꺼번에 정한다 candidates = [] seen = set() for y, x in frontier: for dy, dx in STEPS: ny, nx = y + dy, x + dx if 0 <= ny < r and 0 <= nx < c and grid[ny][nx] == "." and (ny, nx) not in seen: seen.add((ny, nx)) candidates.append((ny, nx)) decided = [] for y, x in candidates: votes = {} for dy, dx in STEPS: ny, nx = y + dy, x + dx if 0 <= ny < r and 0 <= nx < c and grid[ny][nx].isupper(): votes[grid[ny][nx]] = votes.get(grid[ny][nx], 0) + 1 best = max(votes.values()) winners = [ch for ch, v in votes.items() if v == best] decided.append((y, x, winners[0] if len(winners) == 1 else "*")) new_frontier = [] for y, x, ch in decided: grid[y][x] = ch if ch != "*": new_frontier.append((y, x)) # '*'는 퍼지지 않는다 # 2) 시작: 이 분에 시작하는 출발점은 칸이 아직 빈칸일 때만 시작한다 while nxt < len(starts) and starts[nxt][0] == minute: _, letter, y, x = starts[nxt] if grid[y][x] == ".": grid[y][x] = letter new_frontier.append((y, x)) nxt += 1 frontier = new_frontier minute += 1print("\n".join("".join(row) for row in grid))
JavaScriptmain.js · 67 줄
const data = require("fs").readFileSync(0, "utf8").split("\n");const [r, c] = data[0].trim().split(/\s+/).map(Number);const grid = [];const where = new Map(); // 글자 → 칸 번호(y * c + x)for (let y = 0; y < r; y++) { const row = data[1 + y].trim().split(""); row.forEach((ch, x) => { if (ch >= "A" && ch <= "Z") { where.set(ch, y * c + x); row[x] = "."; // 시작하기 전에는 빈칸이다 } }); grid.push(row);}const k = Number(data[1 + r]);const starts = []; // { t, letter, cell }for (let i = 0; i < k; i++) { const [letter, t] = data[2 + r + i].trim().split(/\s+/); starts.push({ t: Number(t), letter, cell: where.get(letter) });}starts.sort((a, b) => a.t - b.t);const isLetter = (ch) => ch >= "A" && ch <= "Z";const STEPS = [[-1, 0], [1, 0], [0, -1], [0, 1]];const mark = new Array(r * c).fill(-1); // 이번 분에 이미 후보로 넣은 칸let frontier = []; // 직전 분에 새로 글자를 얻은 칸들(너비 우선 탐색의 한 겹)let next = 0;let minute = 0;while (frontier.length > 0 || next < starts.length) { if (frontier.length === 0) minute = Math.max(minute, starts[next].t); // 퍼질 것이 없으면 건너뛴다 // 1) 퍼지기: 직전 분 상태로 모든 빈칸을 한꺼번에 정한다 const decided = []; for (const cell of frontier) { const y = Math.floor(cell / c), x = cell % c; for (const [dy, dx] of STEPS) { const ny = y + dy, nx = x + dx; if (ny < 0 || ny >= r || nx < 0 || nx >= c || grid[ny][nx] !== "." || mark[ny * c + nx] === minute) continue; mark[ny * c + nx] = minute; const votes = new Map(); for (const [ey, ex] of STEPS) { const vy = ny + ey, vx = nx + ex; if (vy >= 0 && vy < r && vx >= 0 && vx < c && isLetter(grid[vy][vx])) votes.set(grid[vy][vx], (votes.get(grid[vy][vx]) ?? 0) + 1); } const best = Math.max(...votes.values()); const winners = [...votes].filter(([, v]) => v === best); decided.push([ny, nx, winners.length === 1 ? winners[0][0] : "*"]); } } const newFrontier = []; for (const [y, x, ch] of decided) { grid[y][x] = ch; if (ch !== "*") newFrontier.push(y * c + x); // '*'는 퍼지지 않는다 } // 2) 시작: 이 분에 시작하는 출발점은 칸이 아직 빈칸일 때만 시작한다 while (next < starts.length && starts[next].t === minute) { const { letter, cell } = starts[next++]; const y = Math.floor(cell / c), x = cell % c; if (grid[y][x] === ".") { grid[y][x] = letter; newFrontier.push(cell); } } frontier = newFrontier; minute++;}console.log(grid.map((row) => row.join("")).join("\n"));
TypeScriptmain.ts · 74 줄
import { readFileSync } from "node:fs";const data: string[] = readFileSync(0, "utf8").split("\n");const [r, c] = data[0].trim().split(/\s+/).map(Number);const grid: string[][] = [];const where = new Map<string, number>(); // 글자 → 칸 번호(y * c + x)for (let y = 0; y < r; y++) { const row = data[1 + y].trim().split(""); row.forEach((ch, x) => { if (ch >= "A" && ch <= "Z") { where.set(ch, y * c + x); row[x] = "."; // 시작하기 전에는 빈칸이다 } }); grid.push(row);}const k = Number(data[1 + r]);interface Start { t: number; letter: string; cell: number;}const starts: Start[] = [];for (let i = 0; i < k; i++) { const [letter, t] = data[2 + r + i].trim().split(/\s+/); starts.push({ t: Number(t), letter, cell: where.get(letter)! });}starts.sort((a, b) => a.t - b.t);const isLetter = (ch: string): boolean => ch >= "A" && ch <= "Z";const STEPS: [number, number][] = [[-1, 0], [1, 0], [0, -1], [0, 1]];const mark: number[] = new Array<number>(r * c).fill(-1); // 이번 분에 이미 후보로 넣은 칸let frontier: number[] = []; // 직전 분에 새로 글자를 얻은 칸들(너비 우선 탐색의 한 겹)let next = 0;let minute = 0;while (frontier.length > 0 || next < starts.length) { if (frontier.length === 0) minute = Math.max(minute, starts[next].t); // 퍼질 것이 없으면 건너뛴다 // 1) 퍼지기: 직전 분 상태로 모든 빈칸을 한꺼번에 정한다 const decided: [number, number, string][] = []; for (const cell of frontier) { const y = Math.floor(cell / c), x = cell % c; for (const [dy, dx] of STEPS) { const ny = y + dy, nx = x + dx; if (ny < 0 || ny >= r || nx < 0 || nx >= c || grid[ny][nx] !== "." || mark[ny * c + nx] === minute) continue; mark[ny * c + nx] = minute; const votes = new Map<string, number>(); for (const [ey, ex] of STEPS) { const vy = ny + ey, vx = nx + ex; if (vy >= 0 && vy < r && vx >= 0 && vx < c && isLetter(grid[vy][vx])) votes.set(grid[vy][vx], (votes.get(grid[vy][vx]) ?? 0) + 1); } const best = Math.max(...votes.values()); const winners = [...votes].filter(([, v]) => v === best); decided.push([ny, nx, winners.length === 1 ? winners[0][0] : "*"]); } } const newFrontier: number[] = []; for (const [y, x, ch] of decided) { grid[y][x] = ch; if (ch !== "*") newFrontier.push(y * c + x); // '*'는 퍼지지 않는다 } // 2) 시작: 이 분에 시작하는 출발점은 칸이 아직 빈칸일 때만 시작한다 while (next < starts.length && starts[next].t === minute) { const { letter, cell } = starts[next++]; const y = Math.floor(cell / c), x = cell % c; if (grid[y][x] === ".") { grid[y][x] = letter; newFrontier.push(cell); } } frontier = newFrontier; minute++;}console.log(grid.map((row) => row.join("")).join("\n"));
JavaMain.java · 84 줄
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Arrays;import java.util.Comparator;import java.util.List;public class Main { record Start(int t, char letter, int y, int x) {} public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); String[] first = in.readLine().trim().split("\\s+"); int r = Integer.parseInt(first[0]), c = Integer.parseInt(first[1]); char[][] grid = new char[r][]; int[][] where = new int[26][]; for (int y = 0; y < r; y++) { grid[y] = in.readLine().trim().toCharArray(); for (int x = 0; x < c; x++) if (Character.isUpperCase(grid[y][x])) { where[grid[y][x] - 'A'] = new int[] {y, x}; grid[y][x] = '.'; // 시작하기 전에는 빈칸이다 } } int k = Integer.parseInt(in.readLine().trim()); List<Start> starts = new ArrayList<>(); for (int i = 0; i < k; i++) { String[] p = in.readLine().trim().split("\\s+"); char letter = p[0].charAt(0); int[] pos = where[letter - 'A']; starts.add(new Start(Integer.parseInt(p[1]), letter, pos[0], pos[1])); } starts.sort(Comparator.comparingInt(Start::t)); int[] dy = {-1, 1, 0, 0}, dx = {0, 0, -1, 1}; int[][] mark = new int[r][c]; // 이번 분에 이미 후보로 넣은 칸 for (int[] row : mark) Arrays.fill(row, -1); List<int[]> frontier = new ArrayList<>(); // 직전 분에 새로 글자를 얻은 칸들(너비 우선 탐색의 한 겹) int next = 0, minute = 0; while (!frontier.isEmpty() || next < k) { if (frontier.isEmpty()) minute = Math.max(minute, starts.get(next).t()); // 퍼질 것이 없으면 건너뛴다 // 1) 퍼지기: 직전 분 상태로 모든 빈칸을 한꺼번에 정한다 List<int[]> decided = new ArrayList<>(); // {y, x, 글자} for (int[] cell : frontier) for (int d = 0; d < 4; d++) { int ny = cell[0] + dy[d], nx = cell[1] + dx[d]; if (ny < 0 || ny >= r || nx < 0 || nx >= c || grid[ny][nx] != '.' || mark[ny][nx] == minute) continue; mark[ny][nx] = minute; int[] votes = new int[26]; for (int e = 0; e < 4; e++) { int vy = ny + dy[e], vx = nx + dx[e]; if (vy >= 0 && vy < r && vx >= 0 && vx < c && Character.isUpperCase(grid[vy][vx])) votes[grid[vy][vx] - 'A']++; } int best = 0, winners = 0; char win = '*'; for (int l = 0; l < 26; l++) { if (votes[l] > best) { best = votes[l]; winners = 1; win = (char) ('A' + l); } else if (votes[l] == best && best > 0) winners++; } decided.add(new int[] {ny, nx, winners == 1 ? win : '*'}); } List<int[]> fresh = new ArrayList<>(); for (int[] dcd : decided) { grid[dcd[0]][dcd[1]] = (char) dcd[2]; if (dcd[2] != '*') fresh.add(new int[] {dcd[0], dcd[1]}); // '*'는 퍼지지 않는다 } // 2) 시작: 이 분에 시작하는 출발점은 칸이 아직 빈칸일 때만 시작한다 for (; next < k && starts.get(next).t() == minute; next++) { Start s = starts.get(next); if (grid[s.y()][s.x()] == '.') { grid[s.y()][s.x()] = s.letter(); fresh.add(new int[] {s.y(), s.x()}); } } frontier = fresh; minute++; } StringBuilder out = new StringBuilder(); for (char[] row : grid) out.append(row).append('\n'); System.out.print(out); }}
C#Main.cs · 86 줄
using System;using System.Collections.Generic;using System.Linq;using System.Text;class Program{ static void Main() { int[] first = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToArray(); int r = first[0], c = first[1]; var grid = new char[r][]; var where = new Dictionary<char, (int y, int x)>(); for (int y = 0; y < r; y++) { grid[y] = Console.ReadLine().Trim().ToCharArray(); for (int x = 0; x < c; x++) if (char.IsUpper(grid[y][x])) { where[grid[y][x]] = (y, x); grid[y][x] = '.'; // 시작하기 전에는 빈칸이다 } } int k = int.Parse(Console.ReadLine().Trim()); var starts = new List<(int t, char letter, int y, int x)>(); for (int i = 0; i < k; i++) { string[] p = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); char letter = p[0][0]; var (sy, sx) = where[letter]; starts.Add((int.Parse(p[1]), letter, sy, sx)); } starts = starts.OrderBy(s => s.t).ToList(); int[] dy = { -1, 1, 0, 0 }, dx = { 0, 0, -1, 1 }; bool Inside(int y, int x) => y >= 0 && y < r && x >= 0 && x < c; var mark = new int[r, c]; // 이번 분에 이미 후보로 넣은 칸 for (int y = 0; y < r; y++) for (int x = 0; x < c; x++) mark[y, x] = -1; var frontier = new List<(int y, int x)>(); // 직전 분에 새로 글자를 얻은 칸들(너비 우선 탐색의 한 겹) int next = 0, minute = 0; while (frontier.Count > 0 || next < k) { if (frontier.Count == 0) minute = Math.Max(minute, starts[next].t); // 퍼질 것이 없으면 건너뛴다 // 1) 퍼지기: 직전 분 상태로 모든 빈칸을 한꺼번에 정한다 var decided = new List<(int y, int x, char ch)>(); foreach (var (y, x) in frontier) for (int d = 0; d < 4; d++) { int ny = y + dy[d], nx = x + dx[d]; if (!Inside(ny, nx) || grid[ny][nx] != '.' || mark[ny, nx] == minute) continue; mark[ny, nx] = minute; var votes = new int[26]; for (int e = 0; e < 4; e++) { int vy = ny + dy[e], vx = nx + dx[e]; if (Inside(vy, vx) && char.IsUpper(grid[vy][vx])) votes[grid[vy][vx] - 'A']++; } int best = votes.Max(); bool single = votes.Count(v => v == best) == 1; decided.Add((ny, nx, single ? (char)('A' + Array.IndexOf(votes, best)) : '*')); } var fresh = new List<(int y, int x)>(); foreach (var (y, x, ch) in decided) { grid[y][x] = ch; if (ch != '*') fresh.Add((y, x)); // '*'는 퍼지지 않는다 } // 2) 시작: 이 분에 시작하는 출발점은 칸이 아직 빈칸일 때만 시작한다 for (; next < k && starts[next].t == minute; next++) { var s = starts[next]; if (grid[s.y][s.x] == '.') { grid[s.y][s.x] = s.letter; fresh.Add((s.y, s.x)); } } frontier = fresh; minute++; } var out_ = new StringBuilder(); foreach (var row in grid) out_.Append(row).Append('\n'); Console.Write(out_); }}
C++main.cpp · 78 줄
#include <algorithm>#include <cctype>#include <array>#include <iostream>#include <string>#include <tuple>#include <vector>struct Start { int t; char letter; int y, x;};int main() { int r, c, k; std::cin >> r >> c; std::vector<std::string> grid(r); std::array<std::pair<int, int>, 26> where{}; for (int y = 0; y < r; y++) { std::cin >> grid[y]; for (int x = 0; x < c; x++) if (std::isupper(static_cast<unsigned char>(grid[y][x]))) { where[grid[y][x] - 'A'] = {y, x}; grid[y][x] = '.'; // 시작하기 전에는 빈칸이다 } } std::cin >> k; std::vector<Start> starts(k); for (auto& s : starts) { std::cin >> s.letter >> s.t; std::tie(s.y, s.x) = where[s.letter - 'A']; } std::sort(starts.begin(), starts.end(), [](const Start& a, const Start& b) { return a.t < b.t; }); const int DY[4] = {-1, 1, 0, 0}, DX[4] = {0, 0, -1, 1}; auto inside = [&](int y, int x) { return y >= 0 && y < r && x >= 0 && x < c; }; std::vector<std::vector<int>> mark(r, std::vector<int>(c, -1)); // 이번 분에 이미 후보로 넣은 칸 std::vector<std::pair<int, int>> frontier; // 직전 분에 새로 글자를 얻은 칸들(너비 우선 탐색의 한 겹) std::size_t next = 0; int minute = 0; while (!frontier.empty() || next < starts.size()) { if (frontier.empty()) minute = std::max(minute, starts[next].t); // 퍼질 것이 없으면 건너뛴다 // 1) 퍼지기: 직전 분 상태로 모든 빈칸을 한꺼번에 정한다 std::vector<std::tuple<int, int, char>> decided; for (auto [y, x] : frontier) for (int d = 0; d < 4; d++) { int ny = y + DY[d], nx = x + DX[d]; if (!inside(ny, nx) || grid[ny][nx] != '.' || mark[ny][nx] == minute) continue; mark[ny][nx] = minute; std::array<int, 26> votes{}; for (int e = 0; e < 4; e++) { int vy = ny + DY[e], vx = nx + DX[e]; if (inside(vy, vx) && std::isupper(static_cast<unsigned char>(grid[vy][vx]))) votes[grid[vy][vx] - 'A']++; } int best = *std::max_element(votes.begin(), votes.end()); int winners = static_cast<int>(std::count(votes.begin(), votes.end(), best)); char win = static_cast<char>('A' + (std::max_element(votes.begin(), votes.end()) - votes.begin())); decided.emplace_back(ny, nx, winners == 1 ? win : '*'); } std::vector<std::pair<int, int>> fresh; for (auto [y, x, ch] : decided) { grid[y][x] = ch; if (ch != '*') fresh.emplace_back(y, x); // '*'는 퍼지지 않는다 } // 2) 시작: 이 분에 시작하는 출발점은 칸이 아직 빈칸일 때만 시작한다 for (; next < starts.size() && starts[next].t == minute; next++) { const Start& s = starts[next]; if (grid[s.y][s.x] == '.') { grid[s.y][s.x] = s.letter; fresh.emplace_back(s.y, s.x); } } frontier = std::move(fresh); minute++; } for (const auto& row : grid) std::cout << row << "\n";}
Cmain.c · 97 줄
#include <stdio.h>#include <stdlib.h>#define MAXN 50static char grid[MAXN][MAXN + 2];static int mark[MAXN * MAXN]; /* 이번 분에 이미 후보로 넣은 칸 */static int frontier[MAXN * MAXN], nf; /* 직전 분에 새로 글자를 얻은 칸들(너비 우선 탐색의 한 겹) */static int fresh[MAXN * MAXN], nfresh;static int decY[MAXN * MAXN], decX[MAXN * MAXN];static char decCh[MAXN * MAXN];typedef struct { int t; char letter; int cell;} Start;static int byTime(const void *a, const void *b) { return ((const Start *)a)->t - ((const Start *)b)->t;}int main(void) { int r, c, k; int where[26]; Start starts[26]; scanf("%d %d", &r, &c); for (int y = 0; y < r; y++) { scanf("%51s", grid[y]); for (int x = 0; x < c; x++) if (grid[y][x] >= 'A' && grid[y][x] <= 'Z') { where[grid[y][x] - 'A'] = y * c + x; grid[y][x] = '.'; /* 시작하기 전에는 빈칸이다 */ } } scanf("%d", &k); for (int i = 0; i < k; i++) { char letter[4]; scanf("%3s %d", letter, &starts[i].t); starts[i].letter = letter[0]; starts[i].cell = where[letter[0] - 'A']; } qsort(starts, k, sizeof starts[0], byTime); for (int i = 0; i < r * c; i++) mark[i] = -1; const int DY[4] = {-1, 1, 0, 0}, DX[4] = {0, 0, -1, 1}; int next = 0, minute = 0; nf = 0; while (nf > 0 || next < k) { if (nf == 0 && starts[next].t > minute) minute = starts[next].t; /* 퍼질 것이 없으면 건너뛴다 */ /* 1) 퍼지기: 직전 분 상태로 모든 빈칸을 한꺼번에 정한다 */ int nd = 0; for (int i = 0; i < nf; i++) { int y = frontier[i] / c, x = frontier[i] % c; for (int d = 0; d < 4; d++) { int ny = y + DY[d], nx = x + DX[d]; if (ny < 0 || ny >= r || nx < 0 || nx >= c || grid[ny][nx] != '.' || mark[ny * c + nx] == minute) continue; mark[ny * c + nx] = minute; int votes[26] = {0}; for (int e = 0; e < 4; e++) { int vy = ny + DY[e], vx = nx + DX[e]; if (vy >= 0 && vy < r && vx >= 0 && vx < c && grid[vy][vx] >= 'A' && grid[vy][vx] <= 'Z') votes[grid[vy][vx] - 'A']++; } int best = 0, winners = 0; char win = '*'; for (int l = 0; l < 26; l++) { if (votes[l] > best) { best = votes[l]; winners = 1; win = (char)('A' + l); } else if (votes[l] == best && best > 0) winners++; } decY[nd] = ny; decX[nd] = nx; decCh[nd] = winners == 1 ? win : '*'; nd++; } } nfresh = 0; for (int i = 0; i < nd; i++) { grid[decY[i]][decX[i]] = decCh[i]; if (decCh[i] != '*') fresh[nfresh++] = decY[i] * c + decX[i]; /* '*'는 퍼지지 않는다 */ } /* 2) 시작: 이 분에 시작하는 출발점은 칸이 아직 빈칸일 때만 시작한다 */ while (next < k && starts[next].t == minute) { int y = starts[next].cell / c, x = starts[next].cell % c; if (grid[y][x] == '.') { grid[y][x] = starts[next].letter; fresh[nfresh++] = starts[next].cell; } next++; } for (int i = 0; i < nfresh; i++) frontier[i] = fresh[i]; nf = nfresh; minute++; } for (int y = 0; y < r; y++) puts(grid[y]); return 0;}
Craykonmain.cray · 145 줄
첫줄 = 콘솔.수들읽기();r = 첫줄[0];c = 첫줄[1];글자인가(ch){ 돌려주기 ch >= "A" && ch <= "Z";}// 칸은 수 하나(y * c + x)로 다룬다. 지도는 한 글자짜리 문자열의 2차원 목록grid = [];where = 사전(); // 글자 → 칸 번호반복 (y = 0; y < r; y++){ 줄 = 콘솔.줄읽기().공백제거(); row = []; 반복 (x = 0; x < c; x++) { ch = 줄[x]; 만약 (글자인가(ch)) { where[ch] = y * c + x; ch = "."; // 시작하기 전에는 빈칸이다 } row.넣기(ch); } grid.넣기(row);}k = 콘솔.줄읽기().공백제거().수로변환();starts = []; // [시작 분, 글자, 칸 번호]반복 (i = 0; i < k; i++){ p = 콘솔.줄읽기().공백제거().나누기(" "); starts.넣기([p[1].수로변환(), p[0], where[p[0]]]);}시각순(앞, 뒤){ 돌려주기 앞[0] - 뒤[0];}starts.정렬(시각순);DY = [-1, 1, 0, 0];DX = [0, 0, -1, 1];안인가(y, x){ 돌려주기 y >= 0 && y < r && x >= 0 && x < c;}mark = 새목록(r * c, -1); // 이번 분에 이미 후보로 넣은 칸frontier = []; // 직전 분에 새로 글자를 얻은 칸들(너비 우선 탐색의 한 겹)next = 0;minute = 0;동안 (frontier.개수 > 0 || next < k){ 만약 (frontier.개수 == 0) { minute = 수학.큰수(minute, starts[next][0]); // 퍼질 것이 없으면 건너뛴다 } // 1) 퍼지기: 직전 분 상태로 모든 빈칸을 한꺼번에 정한다 decided = []; // [칸 번호, 글자] 각각 (cell 에서 frontier) { y = 수학.몫(cell, c); x = cell % c; 반복 (d = 0; d < 4; d++) { ny = y + DY[d]; nx = x + DX[d]; 만약 (안인가(ny, nx) && grid[ny][nx] == "." && mark[ny * c + nx] != minute) { mark[ny * c + nx] = minute; votes = 사전(); 반복 (e = 0; e < 4; e++) { vy = ny + DY[e]; vx = nx + DX[e]; 만약 (안인가(vy, vx) && 글자인가(grid[vy][vx])) { ch = grid[vy][vx]; 만약 (votes.있나(ch)) { votes[ch] += 1; } 아니면 { votes[ch] = 1; } } } best = 0; winners = 0; win = "*"; 각각 (ch 에서 votes.열쇠목록) { 만약 (votes[ch] > best) { best = votes[ch]; winners = 1; win = ch; } 아니면 만약 (votes[ch] == best) { winners += 1; } } 만약 (winners > 1) { win = "*"; } decided.넣기([ny * c + nx, win]); } } } fresh = []; 각각 (dcd 에서 decided) { grid[수학.몫(dcd[0], c)][dcd[0] % c] = dcd[1]; 만약 (dcd[1] != "*") { fresh.넣기(dcd[0]); // '*'는 퍼지지 않는다 } } // 2) 시작: 이 분에 시작하는 출발점은 칸이 아직 빈칸일 때만 시작한다 동안 (next < k && starts[next][0] == minute) { cell = starts[next][2]; y = 수학.몫(cell, c); x = cell % c; 만약 (grid[y][x] == ".") { grid[y][x] = starts[next][1]; fresh.넣기(cell); } next += 1; } frontier = fresh; minute += 1;}각각 (row 에서 grid){ 콘솔.쓰기(row.잇기(""));}