A few drops of paint fall on a sheet of R rows and C columns.
'.' is an empty cell, '#' is a cell paint cannot soak into, and an uppercase letter marks the cell where a drop of that letter's color will fall.
For each letter, the time (in minutes) its drop falls is given.
Before its drop falls, that cell also counts as empty.
Two cells are neighbors when they touch up, down, left or right.
Starting at minute 0, one minute at a time, each minute does the following two steps in order.
Step 1 (spread): every empty cell with at least one neighbor holding a letter at the end of the previous minute changes, all at once, looking only at the state at the end of the previous minute.
It becomes the letter that appears most among its neighbors, and if two or more letters tie for most, it becomes '*'.
'*' cells and '#' cells do not count as letters, and a '*' cell never changes again.
Step 2 (fall): a drop that falls this minute turns its cell into its letter only if that cell is still empty.
If its cell has already become another letter or '*', the drop never happened.
At minute 0 there is no previous minute, so only drops fall.
A cell that has become a letter never changes again.
When no cell can change and no drop is left to fall, print the sheet.
Print fallen drops and spread cells as their letter, tied cells as '*', cells that stayed empty as '.', and '#' unchanged.
Input
The first line has R and C, followed by R strings of length C made of '.', '#' and uppercase letters, then a line with the number of drops K, then K lines each with a letter L and its falling time t separated by a space. 1 ≤ R, C ≤ 50, 0 ≤ K ≤ 26, 0 ≤ t ≤ 10,000. The uppercase letters on the map are all different, and the letters on the K lines are exactly the uppercase letters on the map (in any order).
Output
R lines, each a string of length C (the final sheet)
Example 1 · stdin
3 5
A...B
.....
..#..
2
A 0
B 0
stdout
AA*BB
AA*BB
AA#BB
Example 2 · stdin
4 4
.A#.
....
B...
...C
3
A 3
B 0
C 2
stdout
BB#B
BBBB
BBB*
BBBC
main.py
Error List00F8 ↓ · ⇧F8 ↑
Input (stdin)
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
Spreading from several places at once is breadth-first search (BFS) run one layer at a time. Keep only the cells colored in the previous minute (one layer) in the queue, collect their empty neighbors as this minute's candidates, count each candidate's neighboring letters, and decide all of them before coloring any. Only the previous minute's cells need to be in the queue, because the empty neighbors of older cells already changed in the minute after those were colored. The most common trap is coloring neighbors as soon as a cell leaves the queue, as in ordinary BFS — then whichever comes out first takes the cell without competing with other colors arriving in the same minute, so ties ('*') and majorities disappear. Other traps: giving a tie to the alphabetically first letter, putting '*' in the queue so that '*' spreads, and dropping before spreading (then a drop that falls in the very minute the paint spreads onto its cell survives instead of being covered). While nothing is spreading, jump straight to the next drop's time instead of counting each minute (counting all 10,000 minutes is not slow either). To avoid adding one cell twice as a candidate in a minute, store the minute number as the 'added this minute' mark, so it never needs clearing. Handling the tables: Python turns a row into a list of characters with list(row) and counts with a dict. Java uses char[][], an int[26] tally, and sorts start times with Comparator.comparingInt(Start::t). C# uses char[][], new int[r, c] (a rectangular array), a list of named tuples and OrderBy. C++ uses std::vector<std::string> and std::array<int, 26>, finding the top letter and ties with std::max_element and std::count. C uses fixed-size arrays and qsort (its compare function returns negative, 0 or positive). JavaScript and TypeScript count with a Map and Math.max(...votes.values()). Craykon keeps the map as a 2D list of one-character strings, counts with Dict(), and walks votes.Keys to find the largest count and how often it occurs. Start times are sorted by passing a compare function, as in starts.Sort(byTime), and a row is written with row.Join("").
Pythonmain.py · 56 lines
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 lines
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 lines
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 lines
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 lines
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 lines
#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 lines
#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 lines
첫줄 = Console.ReadNumbers();r = 첫줄[0];c = 첫줄[1];글자인가(ch){ return ch >= "A" && ch <= "Z";}// 칸은 수 하나(y * c + x)로 다룬다. 지도는 한 글자짜리 문자열의 2차원 목록grid = [];where = Dict(); // 글자 → 칸 번호for (y = 0; y < r; y++){ 줄 = Console.ReadLine().Trim(); row = []; for (x = 0; x < c; x++) { ch = 줄[x]; if (글자인가(ch)) { where[ch] = y * c + x; ch = "."; // 시작하기 전에는 빈칸이다 } row.Add(ch); } grid.Add(row);}k = Console.ReadLine().Trim().ToNumber();starts = []; // [시작 분, 글자, 칸 번호]for (i = 0; i < k; i++){ p = Console.ReadLine().Trim().Split(" "); starts.Add([p[1].ToNumber(), p[0], where[p[0]]]);}시각순(앞, 뒤){ return 앞[0] - 뒤[0];}starts.Sort(시각순);DY = [-1, 1, 0, 0];DX = [0, 0, -1, 1];안인가(y, x){ return y >= 0 && y < r && x >= 0 && x < c;}mark = NewList(r * c, -1); // 이번 분에 이미 후보로 넣은 칸frontier = []; // 직전 분에 새로 글자를 얻은 칸들(너비 우선 탐색의 한 겹)next = 0;minute = 0;while (frontier.Count > 0 || next < k){ if (frontier.Count == 0) { minute = Mathf.Max(minute, starts[next][0]); // 퍼질 것이 없으면 건너뛴다 } // 1) 퍼지기: 직전 분 상태로 모든 빈칸을 한꺼번에 정한다 decided = []; // [칸 번호, 글자] foreach (cell in frontier) { y = Mathf.Quot(cell, c); x = cell % c; for (d = 0; d < 4; d++) { ny = y + DY[d]; nx = x + DX[d]; if (안인가(ny, nx) && grid[ny][nx] == "." && mark[ny * c + nx] != minute) { mark[ny * c + nx] = minute; votes = Dict(); for (e = 0; e < 4; e++) { vy = ny + DY[e]; vx = nx + DX[e]; if (안인가(vy, vx) && 글자인가(grid[vy][vx])) { ch = grid[vy][vx]; if (votes.Contains(ch)) { votes[ch] += 1; } else { votes[ch] = 1; } } } best = 0; winners = 0; win = "*"; foreach (ch in votes.Keys) { if (votes[ch] > best) { best = votes[ch]; winners = 1; win = ch; } else if (votes[ch] == best) { winners += 1; } } if (winners > 1) { win = "*"; } decided.Add([ny * c + nx, win]); } } } fresh = []; foreach (dcd in decided) { grid[Mathf.Quot(dcd[0], c)][dcd[0] % c] = dcd[1]; if (dcd[1] != "*") { fresh.Add(dcd[0]); // '*'는 퍼지지 않는다 } } // 2) 시작: 이 분에 시작하는 출발점은 칸이 아직 빈칸일 때만 시작한다 while (next < k && starts[next][0] == minute) { cell = starts[next][2]; y = Mathf.Quot(cell, c); x = cell % c; if (grid[y][x] == ".") { grid[y][x] = starts[next][1]; fresh.Add(cell); } next += 1; } frontier = fresh; minute += 1;}foreach (row in grid){ Console.WriteLine(row.Join(""));}