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 行
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 行
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 行
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 行
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 行
#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 行
#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 行
첫줄 = 控制台.读数字();H = 첫줄[0];W = 첫줄[1];grid = [];minute = []; // minute[r][c] = 따뜻해진 시각, 아직이면 -1// 목록으로 만든 큐: 뒤에 넣고, 맨 앞 자리(head)만 뒤로 옮긴다. 줄 번호와 칸 번호를 따로 담는다queueR = [];queueC = [];head = 0;循环 (r = 0; r < H; r++){ 줄 = 控制台.读行().去空白(); grid.添加(줄); minute.添加(新列表(W, -1)); 循环 (c = 0; c < W; c++) { 如果 (줄[c] == "S") { minute[r][c] = 0; queueR.添加(r); queueC.添加(c); } }}counts = [1]; // counts[t] = t분에 새로 따뜻해진 칸의 수dr = [-1, 1, 0, 0];dc = [0, 0, -1, 1];当 (head < queueR.数量){ // 먼저 따뜻해진 칸부터 꺼낸다 r = queueR[head]; c = queueC[head]; head += 1; 循环 (d = 0; d < 4; d++) { nr = r + dr[d]; nc = c + dc[d]; // 교실 밖인지 먼저 묻는다. 묻지 않고 목록 밖을 읽으면 오류로 멈춘다 如果 (nr < 0 || nr >= H || nc < 0 || nc >= W) { 继续; } 如果 (grid[nr][nc] == "#" || minute[nr][nc] != -1) { 继续; } t = minute[r][c] + 1; minute[nr][nc] = t; // 큐에 넣을 때 바로 표시해야 같은 칸이 두 번 들어가지 않는다 如果 (t == counts.数量) { counts.添加(0); } counts[t] += 1; queueR.添加(nr); queueC.添加(nc); }}cold = 0;循环 (r = 0; r < H; r++){ 循环 (c = 0; c < W; c++) { 如果 (grid[r][c] == "." && minute[r][c] == -1) { cold += 1; } }}控制台.输出(counts.数量 - 1);控制台.输出(counts.连接(" "));控制台.输出(cold);