墙上贴着 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);控制台.输出(방법);遍历 (글 在 앞선벽){ 控制台.输出(글);}