A wall is covered with tiles in R rows, C tiles per row.
A tile is either a dark tile (#) or a light tile (.), but some are covered and their color is unknown (?).
Wherever two vertically neighboring rows and two horizontally neighboring columns cross, four tiles meet at one point, and a number is written at that point.
The number is how many of the four tiles meeting at that point are dark.
A color is to be chosen for every covered tile so that all the numbers are right. The colors of visible tiles cannot be changed.
The first line gives R and C.
Each of the next R lines gives one row of the wall as C characters.
Each of the next R - 1 lines gives C - 1 numbers. Among them, the j-th number on the i-th line is the number at the point where the four tiles in rows i and i + 1 and columns j and j + 1 of the wall meet.
First print how many ways there are to choose the colors.
If there is at least one way, also print the earliest wall among the walls that can be made.
Compare two walls row by row from the first row, and within a row from the left tile; at the first place where the colors differ, the wall with the light tile is the earlier wall.
Input
2 ≤ R, C ≤ 10. Each wall character is one of #, . and ?, with no spaces between characters. The numbers are integers from 0 to 4, separated by single spaces
Output
The number of ways on the first line. If there is a way, then R lines with the earliest wall (using only # and .)
Example 1 · stdin
3 4
???.
?#.?
????
2 2 2
2 2 2
stdout
3
..#.
##.#
..#.
Example 2 · stdin
2 2
#?
?.
4
stdout
0
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
Choosing every covered tile and only then checking the numbers means 2^100 cases for 100 tiles, which never finishes. But once the first tile of a row is fixed, there is nothing left to choose in the rest of that row: take the number at the upper-left point and subtract the three tiles already fixed, and you get the tile. So the only things to try are the C tiles of the first row and the R - 1 first tiles of the later rows. That is at most 2^19 cases, and far fewer in practice because a branch is dropped the moment it contradicts a number. Every solution uses recursive functions that choose the first row tile by tile, then for each row choose the first tile and fill in the rest. The light tile is tried first, so the first wall found is the earliest wall. The wall being built lives in a list of lists in Python, an array of arrays in JS/TS, int[][] in Java, int[,] in C#, int grid[10][10] in C, std::vector<std::vector<int>> in C++ and NewList(rows, NewList(cols, 0)) in Craykon. In Python the inner function needs nonlocal to change the variable that counts the ways. TS only knows best as the null first stored in it, even after a function changes it, so inside if (best !== null) it sees never and reports a type error (TS2488). That is why the type is restated with best as string[] | null. Trap one: do not collect the valid walls as strings and take the smallest. By character code # (35) comes before . (46), so in the first example a wall starting with #.#. is chosen. Trap two: a tile fixed by a number must also match a tile that is already visible. Without that check the first example has 11 ways instead of 3. Trap three: the value left after subtracting from the number must be 0 or 1. Rejecting only negatives and letting values above 1 through makes the first example 4. Trap four: fixing the first row does not fix everything. The first tile of each later row must be chosen too. Leaving it always light makes the first example 1. Trap five: choosing every covered tile one by one in Craykon stops on a large wall with a 'Took too long' message.
Pythonmain.py · 58 lines
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 lines
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 lines
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 lines
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 lines
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 lines
#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 lines
#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 lines
// 줄 i의 첫 타일이 정해지면 나머지 타일은 위쪽 숫자가 정해 준다. 맞지 않으면 거짓나머지채우기(i){ for (j = 1; j < 칸수; j++) { v = 숫자[i - 1][j - 1] - 벽[i - 1][j - 1] - 벽[i - 1][j] - 벽[i][j - 1]; if (v < 0 || v > 1) { return false; } if (보임[i][j] != -1 && 보임[i][j] != v) { return false; } 벽[i][j] = v; } return true;}아랫줄들(i){ if (i == 줄수) { 방법 += 1; if (앞선벽.Count == 0) { foreach (줄 in 벽) { 글 = ""; foreach (v in 줄) { if (v == 1) { 글 = 글 + "#"; } else { 글 = 글 + "."; } } 앞선벽.Add(글); } } return; } for (v = 0; v <= 1; v++) { if (보임[i][0] == -1 || 보임[i][0] == v) { 벽[i][0] = v; if (나머지채우기(i)) { 아랫줄들(i + 1); } } }}첫줄(j){ if (j == 칸수) { 아랫줄들(1); return; } for (v = 0; v <= 1; v++) { if (보임[0][j] == -1 || 보임[0][j] == v) { 벽[0][j] = v; 첫줄(j + 1); } }}크기 = Console.ReadNumbers();줄수 = 크기[0];칸수 = 크기[1];// 보임: 1 = 짙은 타일(#), 0 = 옅은 타일(.), -1 = 모르는 타일(?)보임 = [];for (i = 0; i < 줄수; i++){ 글자들 = Console.ReadLine().Trim(); 한줄 = []; for (j = 0; j < 칸수; j++) { if (글자들[j] == "?") { 한줄.Add(-1); } else if (글자들[j] == "#") { 한줄.Add(1); } else { 한줄.Add(0); } } 보임.Add(한줄);}숫자 = [];for (i = 0; i < 줄수 - 1; i++){ 숫자.Add(Console.ReadNumbers());}벽 = NewList(줄수, NewList(칸수, 0));방법 = 0;앞선벽 = [];첫줄(0);Console.WriteLine(방법);foreach (글 in 앞선벽){ Console.WriteLine(글);}