壁にタイルが R 行、一行に C 枚ずつ貼ってある。 タイルは濃いタイル（#）か薄いタイル（.）だが、何枚かは隠れていて色がわからない（?）。 上下に隣り合う二つの行と左右に隣り合う二つの列が交わるところでは四枚のタイルが一点で出会い、その点に数字が一つ書いてある。 数字は、その点で出会う四枚のタイルのうち濃いタイルの数だ。 隠れたタイルごとに色を決めて、すべての数字が合うようにしたい。 見えているタイルの色は変えられない。 一行目に R と C が与えられる。 続く R 行に、壁が一行に C 文字ずつ与えられる。 続く R - 1 行に、数字が一行に C - 1 個ずつ与えられる。 このうち i 行目の j 番目の数字は、壁の i 行目と i + 1 行目、j 列目と j + 1 列目にある四枚のタイルが出会う点の数字だ。 まず、色の決め方が全部で何通りあるかを出力する。 決め方が一つでもあれば、そうして作れる壁のうち最も先の壁も出力する。 二つの壁を一行目から順に、行の中では左のタイルから比べて、初めて色が違う場所で薄いタイルを持つ壁が先の壁だ。
import sysdef main(): data = sys.stdin.read().split() rows, cols = int(data[0]), int(data[1]) # known[i][j]: 1 = 짙은 타일(#), 0 = 옅은 타일(.), -1 = 모르는 타일(?) known = [[-1 if ch == "?" else int(ch == "#") for ch in data[2 + i]] for i in range(rows)] pos = 2 + rows hints = [[int(data[pos + i * (cols - 1) + j]) for j in range(cols - 1)] for i in range(rows - 1)] grid = [[0] * cols for _ in range(rows)] count = 0 best = None def fill_rest(i): """줄 i의 첫 타일이 정해지면 나머지 타일은 위쪽 숫자가 정해 준다. 맞지 않으면 False""" for j in range(1, cols): v = hints[i - 1][j - 1] - grid[i - 1][j - 1] - grid[i - 1][j] - grid[i][j - 1] if v < 0 or v > 1: # 타일은 짙거나 옅을 뿐이다 return False if known[i][j] != -1 and known[i][j] != v: # 이미 보이는 타일과 달라도 안 된다 return False grid[i][j] = v return True def later_rows(i): nonlocal count, best if i == rows: count += 1 if best is None: # 옅은 타일부터 해 보았으니 처음 찾은 벽이 가장 앞선다 best = ["".join(".#"[v] for v in row) for row in grid] return for v in (0, 1): # 둘째 줄부터는 첫 타일만 고른다 if known[i][0] != -1 and known[i][0] != v: continue grid[i][0] = v if fill_rest(i): later_rows(i + 1) def first_row(j): if j == cols: later_rows(1) return for v in (0, 1): # 첫 줄은 타일마다 고른다 if known[0][j] != -1 and known[0][j] != v: continue grid[0][j] = v first_row(j + 1) first_row(0) out = [str(count)] if best is not None: out += best print("\n".join(out))main()
JavaScriptmain.js · 59 行
const data = require("fs").readFileSync(0, "utf8").split(/\s+/).filter(Boolean);const rows = Number(data[0]), cols = Number(data[1]);// known[i][j]: 1 = 짙은 타일(#), 0 = 옅은 타일(.), -1 = 모르는 타일(?)const known = [];for (let i = 0; i < rows; i++) { known.push([...data[2 + i]].map((ch) => (ch === "?" ? -1 : ch === "#" ? 1 : 0)));}const hints = [];let pos = 2 + rows;for (let i = 0; i < rows - 1; i++) { hints.push(data.slice(pos, pos + cols - 1).map(Number)); pos += cols - 1;}const grid = known.map((row) => row.map(() => 0));let count = 0;let best = null;// 줄 i의 첫 타일이 정해지면 나머지 타일은 위쪽 숫자가 정해 준다. 맞지 않으면 falsefunction fillRest(i) { for (let j = 1; j < cols; j++) { const v = hints[i - 1][j - 1] - grid[i - 1][j - 1] - grid[i - 1][j] - grid[i][j - 1]; if (v < 0 || v > 1) return false; // 타일은 짙거나 옅을 뿐이다 if (known[i][j] !== -1 && known[i][j] !== v) return false; // 이미 보이는 타일과 달라도 안 된다 grid[i][j] = v; } return true;}function laterRows(i) { if (i === rows) { count++; // 옅은 타일부터 해 보았으니 처음 찾은 벽이 가장 앞선다 if (best === null) best = grid.map((row) => row.map((v) => ".#"[v]).join("")); return; } for (let v = 0; v <= 1; v++) { // 둘째 줄부터는 첫 타일만 고른다 if (known[i][0] !== -1 && known[i][0] !== v) continue; grid[i][0] = v; if (fillRest(i)) laterRows(i + 1); }}function firstRow(j) { if (j === cols) { laterRows(1); return; } for (let v = 0; v <= 1; v++) { // 첫 줄은 타일마다 고른다 if (known[0][j] !== -1 && known[0][j] !== v) continue; grid[0][j] = v; firstRow(j + 1); }}firstRow(0);const out = [String(count)];if (best !== null) out.push(...best);console.log(out.join("\n"));
TypeScriptmain.ts · 62 行
import { readFileSync } from "node:fs";const data: string[] = readFileSync(0, "utf8").split(/\s+/).filter(Boolean);const rows = Number(data[0]), cols = Number(data[1]);// known[i][j]: 1 = 짙은 타일(#), 0 = 옅은 타일(.), -1 = 모르는 타일(?)const known: number[][] = [];for (let i = 0; i < rows; i++) { known.push([...data[2 + i]].map((ch) => (ch === "?" ? -1 : ch === "#" ? 1 : 0)));}const hints: number[][] = [];let pos = 2 + rows;for (let i = 0; i < rows - 1; i++) { hints.push(data.slice(pos, pos + cols - 1).map(Number)); pos += cols - 1;}const grid: number[][] = known.map((row) => row.map(() => 0));let count = 0;let best: string[] | null = null;// 줄 i의 첫 타일이 정해지면 나머지 타일은 위쪽 숫자가 정해 준다. 맞지 않으면 falsefunction fillRest(i: number): boolean { for (let j = 1; j < cols; j++) { const v = hints[i - 1][j - 1] - grid[i - 1][j - 1] - grid[i - 1][j] - grid[i][j - 1]; if (v < 0 || v > 1) return false; // 타일은 짙거나 옅을 뿐이다 if (known[i][j] !== -1 && known[i][j] !== v) return false; // 이미 보이는 타일과 달라도 안 된다 grid[i][j] = v; } return true;}function laterRows(i: number): void { if (i === rows) { count++; // 옅은 타일부터 해 보았으니 처음 찾은 벽이 가장 앞선다 if (best === null) best = grid.map((row) => row.map((v) => ".#"[v]).join("")); return; } for (let v = 0; v <= 1; v++) { // 둘째 줄부터는 첫 타일만 고른다 if (known[i][0] !== -1 && known[i][0] !== v) continue; grid[i][0] = v; if (fillRest(i)) laterRows(i + 1); }}function firstRow(j: number): void { if (j === cols) { laterRows(1); return; } for (let v = 0; v <= 1; v++) { // 첫 줄은 타일마다 고른다 if (known[0][j] !== -1 && known[0][j] !== v) continue; grid[0][j] = v; firstRow(j + 1); }}firstRow(0);const out: string[] = [String(count)];// 함수 안에서 바꾼 best를 TS는 여전히 null로만 알고 있어서, 타입을 다시 알려 준다const found = best as string[] | null;if (found !== null) out.push(...found);console.log(out.join("\n"));
JavaMain.java · 75 行
import java.io.*;import java.util.*;public class Main { static int rows, cols, count = 0; static int[][] known, hints, grid; // known: 1 = 짙은 타일(#), 0 = 옅은 타일(.), -1 = 모르는 타일(?) static String[] best = null; // 줄 i의 첫 타일이 정해지면 나머지 타일은 위쪽 숫자가 정해 준다. 맞지 않으면 false static boolean fillRest(int i) { for (int j = 1; j < cols; j++) { int v = hints[i - 1][j - 1] - grid[i - 1][j - 1] - grid[i - 1][j] - grid[i][j - 1]; if (v < 0 || v > 1) return false; // 타일은 짙거나 옅을 뿐이다 if (known[i][j] != -1 && known[i][j] != v) return false; // 이미 보이는 타일과 달라도 안 된다 grid[i][j] = v; } return true; } static void laterRows(int i) { if (i == rows) { count++; if (best == null) { // 옅은 타일부터 해 보았으니 처음 찾은 벽이 가장 앞선다 best = new String[rows]; for (int r = 0; r < rows; r++) { StringBuilder sb = new StringBuilder(); for (int c = 0; c < cols; c++) sb.append(grid[r][c] == 1 ? '#' : '.'); best[r] = sb.toString(); } } return; } for (int v = 0; v <= 1; v++) { // 둘째 줄부터는 첫 타일만 고른다 if (known[i][0] != -1 && known[i][0] != v) continue; grid[i][0] = v; if (fillRest(i)) laterRows(i + 1); } } static void firstRow(int j) { if (j == cols) { laterRows(1); return; } for (int v = 0; v <= 1; v++) { // 첫 줄은 타일마다 고른다 if (known[0][j] != -1 && known[0][j] != v) continue; grid[0][j] = v; firstRow(j + 1); } } public static void main(String[] args) { Scanner in = new Scanner(System.in); rows = in.nextInt(); cols = in.nextInt(); known = new int[rows][cols]; grid = new int[rows][cols]; for (int i = 0; i < rows; i++) { String line = in.next(); for (int j = 0; j < cols; j++) { char ch = line.charAt(j); known[i][j] = ch == '?' ? -1 : ch == '#' ? 1 : 0; } } hints = new int[rows - 1][cols - 1]; for (int i = 0; i < rows - 1; i++) for (int j = 0; j < cols - 1; j++) hints[i][j] = in.nextInt(); firstRow(0); StringBuilder out = new StringBuilder(); out.append(count).append('\n'); if (best != null) for (String line : best) out.append(line).append('\n'); System.out.print(out); }}
C#Main.cs · 87 行
using System;using System.Text;class Program{ static int rows, cols, count = 0; static int[,] known, hints, grid; // known: 1 = 짙은 타일(#), 0 = 옅은 타일(.), -1 = 모르는 타일(?) static string[] best = null; // 줄 i의 첫 타일이 정해지면 나머지 타일은 위쪽 숫자가 정해 준다. 맞지 않으면 false static bool FillRest(int i) { for (int j = 1; j < cols; j++) { int v = hints[i - 1, j - 1] - grid[i - 1, j - 1] - grid[i - 1, j] - grid[i, j - 1]; if (v < 0 || v > 1) return false; // 타일은 짙거나 옅을 뿐이다 if (known[i, j] != -1 && known[i, j] != v) return false; // 이미 보이는 타일과 달라도 안 된다 grid[i, j] = v; } return true; } static void LaterRows(int i) { if (i == rows) { count++; if (best == null) // 옅은 타일부터 해 보았으니 처음 찾은 벽이 가장 앞선다 { best = new string[rows]; for (int r = 0; r < rows; r++) { var sb = new StringBuilder(); for (int c = 0; c < cols; c++) sb.Append(grid[r, c] == 1 ? '#' : '.'); best[r] = sb.ToString(); } } return; } for (int v = 0; v <= 1; v++) // 둘째 줄부터는 첫 타일만 고른다 { if (known[i, 0] != -1 && known[i, 0] != v) continue; grid[i, 0] = v; if (FillRest(i)) LaterRows(i + 1); } } static void FirstRow(int j) { if (j == cols) { LaterRows(1); return; } for (int v = 0; v <= 1; v++) // 첫 줄은 타일마다 고른다 { if (known[0, j] != -1 && known[0, j] != v) continue; grid[0, j] = v; FirstRow(j + 1); } } static void Main() { string[] tokens = Console.In.ReadToEnd().Split((char[])null, StringSplitOptions.RemoveEmptyEntries); rows = int.Parse(tokens[0]); cols = int.Parse(tokens[1]); known = new int[rows, cols]; grid = new int[rows, cols]; for (int i = 0; i < rows; i++) for (int j = 0; j < cols; j++) { char ch = tokens[2 + i][j]; known[i, j] = ch == '?' ? -1 : ch == '#' ? 1 : 0; } hints = new int[rows - 1, cols - 1]; int pos = 2 + rows; for (int i = 0; i < rows - 1; i++) for (int j = 0; j < cols - 1; j++) hints[i, j] = int.Parse(tokens[pos++]); FirstRow(0); var output = new StringBuilder(); output.Append(count).Append('\n'); if (best != null) foreach (string line in best) output.Append(line).Append('\n'); Console.Write(output); }}
C++main.cpp · 67 行
#include <iostream>#include <string>#include <vector>int rows, cols, count = 0;std::vector<std::vector<int>> known, hints, grid; // known: 1 = 짙은 타일(#), 0 = 옅은 타일(.), -1 = 모르는 타일(?)std::vector<std::string> best;// 줄 i의 첫 타일이 정해지면 나머지 타일은 위쪽 숫자가 정해 준다. 맞지 않으면 falsebool fillRest(int i) { for (int j = 1; j < cols; j++) { int v = hints[i - 1][j - 1] - grid[i - 1][j - 1] - grid[i - 1][j] - grid[i][j - 1]; if (v < 0 || v > 1) return false; // 타일은 짙거나 옅을 뿐이다 if (known[i][j] != -1 && known[i][j] != v) return false; // 이미 보이는 타일과 달라도 안 된다 grid[i][j] = v; } return true;}void laterRows(int i) { if (i == rows) { count++; if (best.empty()) { // 옅은 타일부터 해 보았으니 처음 찾은 벽이 가장 앞선다 for (const auto& row : grid) { std::string line; for (int v : row) line += v ? '#' : '.'; best.push_back(line); } } return; } for (int v = 0; v <= 1; v++) { // 둘째 줄부터는 첫 타일만 고른다 if (known[i][0] != -1 && known[i][0] != v) continue; grid[i][0] = v; if (fillRest(i)) laterRows(i + 1); }}void firstRow(int j) { if (j == cols) { laterRows(1); return; } for (int v = 0; v <= 1; v++) { // 첫 줄은 타일마다 고른다 if (known[0][j] != -1 && known[0][j] != v) continue; grid[0][j] = v; firstRow(j + 1); }}int main() { std::cin >> rows >> cols; known.assign(rows, std::vector<int>(cols)); grid.assign(rows, std::vector<int>(cols, 0)); for (int i = 0; i < rows; i++) { std::string line; std::cin >> line; for (int j = 0; j < cols; j++) known[i][j] = line[j] == '?' ? -1 : line[j] == '#' ? 1 : 0; } hints.assign(rows - 1, std::vector<int>(cols - 1)); for (auto& row : hints) for (int& h : row) std::cin >> h; firstRow(0); std::cout << count << '\n'; for (const auto& line : best) std::cout << line << '\n';}
Cmain.c · 69 行
#include <stdio.h>#include <string.h>#define MAX 10static int rows, cols, count = 0, found = 0;static int known[MAX][MAX]; /* 1 = 짙은 타일(#), 0 = 옅은 타일(.), -1 = 모르는 타일(?) */static int hints[MAX][MAX], grid[MAX][MAX], best[MAX][MAX];/* 줄 i의 첫 타일이 정해지면 나머지 타일은 위쪽 숫자가 정해 준다. 맞지 않으면 0 */static int fill_rest(int i) { for (int j = 1; j < cols; j++) { int v = hints[i - 1][j - 1] - grid[i - 1][j - 1] - grid[i - 1][j] - grid[i][j - 1]; if (v < 0 || v > 1) return 0; /* 타일은 짙거나 옅을 뿐이다 */ if (known[i][j] != -1 && known[i][j] != v) return 0; /* 이미 보이는 타일과 달라도 안 된다 */ grid[i][j] = v; } return 1;}static void later_rows(int i) { if (i == rows) { count++; if (!found) { /* 옅은 타일부터 해 보았으니 처음 찾은 벽이 가장 앞선다 */ found = 1; memcpy(best, grid, sizeof grid); } return; } for (int v = 0; v <= 1; v++) { /* 둘째 줄부터는 첫 타일만 고른다 */ if (known[i][0] != -1 && known[i][0] != v) continue; grid[i][0] = v; if (fill_rest(i)) later_rows(i + 1); }}static void first_row(int j) { if (j == cols) { later_rows(1); return; } for (int v = 0; v <= 1; v++) { /* 첫 줄은 타일마다 고른다 */ if (known[0][j] != -1 && known[0][j] != v) continue; grid[0][j] = v; first_row(j + 1); }}int main(void) { char line[MAX + 2]; if (scanf("%d %d", &rows, &cols) != 2) return 0; for (int i = 0; i < rows; i++) { if (scanf("%11s", line) != 1) return 0; for (int j = 0; j < cols; j++) known[i][j] = line[j] == '?' ? -1 : line[j] == '#' ? 1 : 0; } for (int i = 0; i < rows - 1; i++) for (int j = 0; j < cols - 1; j++) if (scanf("%d", &hints[i][j]) != 1) return 0; first_row(0); printf("%d\n", count); if (found) { for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) putchar(best[i][j] ? '#' : '.'); putchar('\n'); } } return 0;}
Craykonmain.cray · 116 行
// 줄 i의 첫 타일이 정해지면 나머지 타일은 위쪽 숫자가 정해 준다. 맞지 않으면 거짓나머지채우기(i){ 繰り返す (j = 1; j < 칸수; j++) { v = 숫자[i - 1][j - 1] - 벽[i - 1][j - 1] - 벽[i - 1][j] - 벽[i][j - 1]; もし (v < 0 || v > 1) { 返す 偽; } もし (보임[i][j] != -1 && 보임[i][j] != v) { 返す 偽; } 벽[i][j] = v; } 返す 真;}아랫줄들(i){ もし (i == 줄수) { 방법 += 1; もし (앞선벽.個数 == 0) { それぞれ (줄 の中 벽) { 글 = ""; それぞれ (v の中 줄) { もし (v == 1) { 글 = 글 + "#"; } でなければ { 글 = 글 + "."; } } 앞선벽.追加(글); } } 返す; } 繰り返す (v = 0; v <= 1; v++) { もし (보임[i][0] == -1 || 보임[i][0] == v) { 벽[i][0] = v; もし (나머지채우기(i)) { 아랫줄들(i + 1); } } }}첫줄(j){ もし (j == 칸수) { 아랫줄들(1); 返す; } 繰り返す (v = 0; v <= 1; v++) { もし (보임[0][j] == -1 || 보임[0][j] == v) { 벽[0][j] = v; 첫줄(j + 1); } }}크기 = コンソール.数読み();줄수 = 크기[0];칸수 = 크기[1];// 보임: 1 = 짙은 타일(#), 0 = 옅은 타일(.), -1 = 모르는 타일(?)보임 = [];繰り返す (i = 0; i < 줄수; i++){ 글자들 = コンソール.行読み().空白除去(); 한줄 = []; 繰り返す (j = 0; j < 칸수; j++) { もし (글자들[j] == "?") { 한줄.追加(-1); } でなければ もし (글자들[j] == "#") { 한줄.追加(1); } でなければ { 한줄.追加(0); } } 보임.追加(한줄);}숫자 = [];繰り返す (i = 0; i < 줄수 - 1; i++){ 숫자.追加(コンソール.数読み());}벽 = 新リスト(줄수, 新リスト(칸수, 0));방법 = 0;앞선벽 = [];첫줄(0);コンソール.書く(방법);それぞれ (글 の中 앞선벽){ コンソール.書く(글);}