On a winter morning, a classroom of H rows and W columns has one stove.
On the map, '.' is a floor cell, '#' is a cell with a bookshelf, and 'S' is the cell with the stove.
At minute 0 only the stove cell is warm.
Each time one minute passes, every floor cell that touches a warm cell on its upper, lower, left or right side becomes warm.
A bookshelf cell never becomes warm, and warmth cannot pass through a bookshelf.
Warmth does not leave the classroom. There is no cell above the top row, below the bottom row, left of the leftmost column or right of the rightmost column.
A cell that has become warm stays warm.
Let T be the last minute at which some cell newly becomes warm. If no cell other than the stove cell becomes warm, T is 0.
On the first line print T.
On the second line print the number of cells that newly became warm at minute 0, minute 1, …, minute T, in order, separated by single spaces. The value for minute 0 is always 1, the stove cell itself.
On the third line print the number of floor cells that never become warm.
Input
The first line has H and W separated by one space. Each of the next H lines is one row of the map, a string of length W made only of '.', '#' and 'S'. 1 ≤ H ≤ 20, 1 ≤ W ≤ 20. There is exactly one 'S' on the whole map
Output
Three lines. T on the first line, the T + 1 counts of newly warm cells for minutes 0 to T on the second, and the number of floor cells that never become warm on the third
Example 1 · stdin
4 5
S..#.
.#.##
....#
...#.
stdout
5
1 2 2 3 2 2
2
Example 2 · stdin
1 4
.S#.
stdout
1
1 1
1
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
Put the stove cell in a queue, take cells out from the front one at a time, look at the four neighbours, and for each cell reached for the first time write 'minute of the cell taken out + 1' and add it to the back of the queue. Keep the four directions in two arrays, dr = [-1, 1, 0, 0] and dc = [0, 0, -1, 1], and one loop covers them. For the queue, use Python deque (popleft), Java ArrayDeque (pollFirst), C# Queue<T> (Dequeue) and C++ std::queue (look with front, remove with pop); JS, TS, C and Craykon add to the back of an array and only move one 'front position' number forward. The languages differ most in what happens when you read a cell outside the classroom. Trap one: if you leave out 0 <= nr and only ask nr < H, Python does not stop. grid[-1] is the last row, so warmth goes through the wall and comes out on the opposite side. In example 2 the cell left of the one left of the stove is read as the rightmost cell, giving 2, then 1 1 1, then 0, and example 1 becomes 1 4 4 3 1 1 and 0. In JS and TS grid[-1] is undefined, so the following [nc] stops with a TypeError, and Craykon also stops with an error saying the list only has positions 0 to 3. Java and C# stop with an exception too, but [] in C and C++ does not check the range: reading outside an array is undefined behaviour, so nothing is promised about what happens. So all eight solutions ask the four range questions before reading the map. Trap two: if you mark a cell as warm when it is taken out of the queue instead of when it is put in, a cell that receives warmth from two neighbours in the same minute enters the queue twice and is counted twice. The second line of example 1 becomes 1 2 2 3 4 3. Trap three: if you take from the back (JS pop()), it is a stack, not a queue, and it digs into far cells before near ones. Example 1 becomes 7 and 1 2 1 1 1 3 2 1. JS shift() does take from the front too. With at most 400 cells, as here, there is no difference, but measured on the judge's Node 22, putting in 200,000 items and taking them all out with shift() took about 3 seconds, while moving a position number took under 0.01 seconds.
Pythonmain.py · 33 lines
import sysfrom collections import dequelines = sys.stdin.read().split("\n")H, W = map(int, lines[0].split())grid = lines[1:1 + H]minute = [[-1] * W for _ in range(H)] # minute[r][c] = 따뜻해진 시각, 아직이면 -1queue = deque()for r in range(H): for c in range(W): if grid[r][c] == "S": minute[r][c] = 0 queue.append((r, c))counts = [1] # counts[t] = t분에 새로 따뜻해진 칸의 수while queue: r, c = queue.popleft() # 먼저 따뜻해진 칸부터 꺼낸다 for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)): nr, nc = r + dr, c + dc # 교실 밖인지 먼저 묻는다. Python의 grid[-1]은 오류가 아니라 맨 끝 줄이다 if 0 <= nr < H and 0 <= nc < W and grid[nr][nc] != "#" and minute[nr][nc] == -1: t = minute[r][c] + 1 minute[nr][nc] = t # 큐에 넣을 때 바로 표시해야 같은 칸이 두 번 들어가지 않는다 if t == len(counts): counts.append(0) counts[t] += 1 queue.append((nr, nc))cold = sum(1 for r in range(H) for c in range(W) if grid[r][c] == "." and minute[r][c] == -1)print(len(counts) - 1)print(" ".join(map(str, counts)))print(cold)
JavaScriptmain.js · 46 lines
const lines = require("fs").readFileSync(0, "utf8").split("\n");const [H, W] = lines[0].trim().split(" ").map(Number);const grid = lines.slice(1, 1 + H);// minute[r][c] = 따뜻해진 시각, 아직이면 -1const minute = Array.from({ length: H }, () => new Array(W).fill(-1));// JS에는 큐가 따로 없다. 배열 뒤에 넣고, 맨 앞 자리(head)만 뒤로 옮긴다const queue = [];let head = 0;for (let r = 0; r < H; r++) { for (let c = 0; c < W; c++) { if (grid[r][c] === "S") { minute[r][c] = 0; queue.push([r, c]); } }}const counts = [1]; // counts[t] = t분에 새로 따뜻해진 칸의 수const dr = [-1, 1, 0, 0];const dc = [0, 0, -1, 1];while (head < queue.length) { const [r, c] = queue[head++]; // 먼저 따뜻해진 칸부터 꺼낸다 for (let d = 0; d < 4; d++) { const nr = r + dr[d]; const nc = c + dc[d]; // 교실 밖인지 먼저 묻는다. grid[-1]은 undefined라서 그 뒤의 [nc]에서 오류가 난다 if (nr < 0 || nr >= H || nc < 0 || nc >= W) continue; if (grid[nr][nc] === "#" || minute[nr][nc] !== -1) continue; const t = minute[r][c] + 1; minute[nr][nc] = t; // 큐에 넣을 때 바로 표시해야 같은 칸이 두 번 들어가지 않는다 if (t === counts.length) counts.push(0); counts[t]++; queue.push([nr, nc]); }}let cold = 0;for (let r = 0; r < H; r++) { for (let c = 0; c < W; c++) { if (grid[r][c] === "." && minute[r][c] === -1) cold++; }}console.log(counts.length - 1);console.log(counts.join(" "));console.log(cold);
TypeScriptmain.ts · 48 lines
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const [H, W]: number[] = lines[0].trim().split(" ").map(Number);const grid: string[] = lines.slice(1, 1 + H);// minute[r][c] = 따뜻해진 시각, 아직이면 -1const minute: number[][] = Array.from({ length: H }, (): number[] => new Array<number>(W).fill(-1));// TS에도 큐가 따로 없다. 배열 뒤에 넣고, 맨 앞 자리(head)만 뒤로 옮긴다const queue: [number, number][] = [];let head = 0;for (let r = 0; r < H; r++) { for (let c = 0; c < W; c++) { if (grid[r][c] === "S") { minute[r][c] = 0; queue.push([r, c]); } }}const counts: number[] = [1]; // counts[t] = t분에 새로 따뜻해진 칸의 수const dr: number[] = [-1, 1, 0, 0];const dc: number[] = [0, 0, -1, 1];while (head < queue.length) { const [r, c] = queue[head++]; // 먼저 따뜻해진 칸부터 꺼낸다 for (let d = 0; d < 4; d++) { const nr = r + dr[d]; const nc = c + dc[d]; // 교실 밖인지 먼저 묻는다. grid[-1]은 undefined라서 그 뒤의 [nc]에서 오류가 난다 if (nr < 0 || nr >= H || nc < 0 || nc >= W) continue; if (grid[nr][nc] === "#" || minute[nr][nc] !== -1) continue; const t = minute[r][c] + 1; minute[nr][nc] = t; // 큐에 넣을 때 바로 표시해야 같은 칸이 두 번 들어가지 않는다 if (t === counts.length) counts.push(0); counts[t]++; queue.push([nr, nc]); }}let cold = 0;for (let r = 0; r < H; r++) { for (let c = 0; c < W; c++) { if (grid[r][c] === "." && minute[r][c] === -1) cold++; }}console.log(counts.length - 1);console.log(counts.join(" "));console.log(cold);
JavaMain.java · 64 lines
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayDeque;import java.util.Arrays;public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); String[] first = in.readLine().trim().split(" "); int H = Integer.parseInt(first[0]); int W = Integer.parseInt(first[1]); char[][] grid = new char[H][]; int[][] minute = new int[H][W]; // minute[r][c] = 따뜻해진 시각, 아직이면 -1 ArrayDeque<int[]> queue = new ArrayDeque<>(); for (int r = 0; r < H; r++) { grid[r] = in.readLine().trim().toCharArray(); Arrays.fill(minute[r], -1); for (int c = 0; c < W; c++) { if (grid[r][c] == 'S') { minute[r][c] = 0; queue.addLast(new int[] {r, c}); } } } int[] counts = new int[H * W]; // counts[t] = t분에 새로 따뜻해진 칸의 수 counts[0] = 1; int last = 0; // 마지막으로 새 칸이 따뜻해진 시각 int[] dr = {-1, 1, 0, 0}; int[] dc = {0, 0, -1, 1}; while (!queue.isEmpty()) { int[] cell = queue.pollFirst(); // 먼저 따뜻해진 칸부터 꺼낸다 int r = cell[0], c = cell[1]; for (int d = 0; d < 4; d++) { int nr = r + dr[d]; int nc = c + dc[d]; // 교실 밖인지 먼저 묻는다. 묻지 않으면 ArrayIndexOutOfBoundsException으로 멈춘다 if (nr < 0 || nr >= H || nc < 0 || nc >= W) continue; if (grid[nr][nc] == '#' || minute[nr][nc] != -1) continue; int t = minute[r][c] + 1; minute[nr][nc] = t; // 큐에 넣을 때 바로 표시해야 같은 칸이 두 번 들어가지 않는다 counts[t]++; last = t; queue.addLast(new int[] {nr, nc}); } } int cold = 0; for (int r = 0; r < H; r++) { for (int c = 0; c < W; c++) { if (grid[r][c] == '.' && minute[r][c] == -1) cold++; } } StringBuilder out = new StringBuilder(); out.append(last).append('\n'); for (int t = 0; t <= last; t++) { if (t > 0) out.append(' '); out.append(counts[t]); } out.append('\n').append(cold); System.out.println(out); }}
C#Main.cs · 61 lines
using System;using System.Collections.Generic;class Program{ static void Main() { string[] first = Console.ReadLine().Trim().Split(' '); int H = int.Parse(first[0]); int W = int.Parse(first[1]); string[] grid = new string[H]; int[,] minute = new int[H, W]; // minute[r, c] = 따뜻해진 시각, 아직이면 -1 var queue = new Queue<(int r, int c)>(); for (int r = 0; r < H; r++) { grid[r] = Console.ReadLine().Trim(); for (int c = 0; c < W; c++) { minute[r, c] = -1; if (grid[r][c] == 'S') { minute[r, c] = 0; queue.Enqueue((r, c)); } } } var counts = new List<int> { 1 }; // counts[t] = t분에 새로 따뜻해진 칸의 수 int[] dr = { -1, 1, 0, 0 }; int[] dc = { 0, 0, -1, 1 }; while (queue.Count > 0) { var (r, c) = queue.Dequeue(); // 먼저 따뜻해진 칸부터 꺼낸다 for (int d = 0; d < 4; d++) { int nr = r + dr[d]; int nc = c + dc[d]; // 교실 밖인지 먼저 묻는다. 묻지 않으면 IndexOutOfRangeException으로 멈춘다 if (nr < 0 || nr >= H || nc < 0 || nc >= W) continue; if (grid[nr][nc] == '#' || minute[nr, nc] != -1) continue; int t = minute[r, c] + 1; minute[nr, nc] = t; // 큐에 넣을 때 바로 표시해야 같은 칸이 두 번 들어가지 않는다 if (t == counts.Count) counts.Add(0); counts[t]++; queue.Enqueue((nr, nc)); } } int cold = 0; for (int r = 0; r < H; r++) { for (int c = 0; c < W; c++) { if (grid[r][c] == '.' && minute[r, c] == -1) cold++; } } Console.WriteLine(counts.Count - 1); Console.WriteLine(string.Join(" ", counts)); Console.WriteLine(cold); }}
C++main.cpp · 57 lines
#include <iostream>#include <queue>#include <string>#include <utility>#include <vector>using namespace std;int main() { int H, W; cin >> H >> W; vector<string> grid(H); vector<vector<int>> minute(H, vector<int>(W, -1)); // 따뜻해진 시각, 아직이면 -1 queue<pair<int, int>> q; for (int r = 0; r < H; r++) { cin >> grid[r]; for (int c = 0; c < W; c++) { if (grid[r][c] == 'S') { minute[r][c] = 0; q.push({r, c}); } } } vector<int> counts = {1}; // counts[t] = t분에 새로 따뜻해진 칸의 수 const int dr[4] = {-1, 1, 0, 0}; const int dc[4] = {0, 0, -1, 1}; while (!q.empty()) { auto [r, c] = q.front(); // 먼저 따뜻해진 칸부터 꺼낸다 q.pop(); // pop()은 값을 돌려주지 않는다 for (int d = 0; d < 4; d++) { int nr = r + dr[d]; int nc = c + dc[d]; // 교실 밖인지 먼저 묻는다. C++의 []는 범위를 확인하지 않고, 배열 밖을 읽으면 정의되지 않은 동작이다 if (nr < 0 || nr >= H || nc < 0 || nc >= W) continue; if (grid[nr][nc] == '#' || minute[nr][nc] != -1) continue; int t = minute[r][c] + 1; minute[nr][nc] = t; // 큐에 넣을 때 바로 표시해야 같은 칸이 두 번 들어가지 않는다 if (t == (int)counts.size()) counts.push_back(0); counts[t]++; q.push({nr, nc}); } } int cold = 0; for (int r = 0; r < H; r++) { for (int c = 0; c < W; c++) { if (grid[r][c] == '.' && minute[r][c] == -1) cold++; } } cout << counts.size() - 1 << '\n'; for (size_t t = 0; t < counts.size(); t++) { if (t > 0) cout << ' '; cout << counts[t]; } cout << '\n' << cold << '\n'; return 0;}
Cmain.c · 62 lines
#include <stdio.h>#define MAXS 20int main(void) { int H, W; static char grid[MAXS][MAXS + 1]; static int minute[MAXS][MAXS]; /* 따뜻해진 시각, 아직이면 -1 */ static int queue_r[MAXS * MAXS]; /* 배열로 만든 큐: tail 자리에 넣고 head 자리에서 꺼낸다 */ static int queue_c[MAXS * MAXS]; static int counts[MAXS * MAXS]; /* counts[t] = t분에 새로 따뜻해진 칸의 수 */ int head = 0, tail = 0, last = 0; scanf("%d %d", &H, &W); for (int r = 0; r < H; r++) { scanf("%20s", grid[r]); for (int c = 0; c < W; c++) { minute[r][c] = -1; if (grid[r][c] == 'S') { minute[r][c] = 0; queue_r[tail] = r; queue_c[tail] = c; tail++; } } } counts[0] = 1; const int dr[4] = {-1, 1, 0, 0}; const int dc[4] = {0, 0, -1, 1}; while (head < tail) { int r = queue_r[head], c = queue_c[head]; /* 먼저 따뜻해진 칸부터 꺼낸다 */ head++; for (int d = 0; d < 4; d++) { int nr = r + dr[d]; int nc = c + dc[d]; /* 교실 밖인지 먼저 묻는다. C는 범위를 확인하지 않고, 배열 밖을 읽으면 정의되지 않은 동작이다 */ if (nr < 0 || nr >= H || nc < 0 || nc >= W) continue; if (grid[nr][nc] == '#' || minute[nr][nc] != -1) continue; int t = minute[r][c] + 1; minute[nr][nc] = t; /* 큐에 넣을 때 바로 표시해야 같은 칸이 두 번 들어가지 않는다 */ counts[t]++; last = t; queue_r[tail] = nr; queue_c[tail] = nc; tail++; } } int cold = 0; for (int r = 0; r < H; r++) { for (int c = 0; c < W; c++) { if (grid[r][c] == '.' && minute[r][c] == -1) cold++; } } printf("%d\n", last); for (int t = 0; t <= last; t++) { printf(t > 0 ? " %d" : "%d", counts[t]); } printf("\n%d\n", cold); return 0;}
Craykonmain.cray · 73 lines
첫줄 = Console.ReadNumbers();H = 첫줄[0];W = 첫줄[1];grid = [];minute = []; // minute[r][c] = 따뜻해진 시각, 아직이면 -1// 목록으로 만든 큐: 뒤에 넣고, 맨 앞 자리(head)만 뒤로 옮긴다. 줄 번호와 칸 번호를 따로 담는다queueR = [];queueC = [];head = 0;for (r = 0; r < H; r++){ 줄 = Console.ReadLine().Trim(); grid.Add(줄); minute.Add(NewList(W, -1)); for (c = 0; c < W; c++) { if (줄[c] == "S") { minute[r][c] = 0; queueR.Add(r); queueC.Add(c); } }}counts = [1]; // counts[t] = t분에 새로 따뜻해진 칸의 수dr = [-1, 1, 0, 0];dc = [0, 0, -1, 1];while (head < queueR.Count){ // 먼저 따뜻해진 칸부터 꺼낸다 r = queueR[head]; c = queueC[head]; head += 1; for (d = 0; d < 4; d++) { nr = r + dr[d]; nc = c + dc[d]; // 교실 밖인지 먼저 묻는다. 묻지 않고 목록 밖을 읽으면 오류로 멈춘다 if (nr < 0 || nr >= H || nc < 0 || nc >= W) { continue; } if (grid[nr][nc] == "#" || minute[nr][nc] != -1) { continue; } t = minute[r][c] + 1; minute[nr][nc] = t; // 큐에 넣을 때 바로 표시해야 같은 칸이 두 번 들어가지 않는다 if (t == counts.Count) { counts.Add(0); } counts[t] += 1; queueR.Add(nr); queueC.Add(nc); }}cold = 0;for (r = 0; r < H; r++){ for (c = 0; c < W; c++) { if (grid[r][c] == "." && minute[r][c] == -1) { cold += 1; } }}Console.WriteLine(counts.Count - 1);Console.WriteLine(counts.Join(" "));Console.WriteLine(cold);