// David Poeschl import java.util.*; public class NonogramsDavid { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int rowCount = scan.nextInt(); int columnCount = scan.nextInt(); // Store everything 1-based to align with the DP table. int[][] rows = new int[rowCount + 1][]; for (int i = 1; i <= rowCount; i++) { int entriesCount = scan.nextInt(); rows[i] = new int[entriesCount + 1]; for (int j = 1; j <= entriesCount; j++) rows[i][j] = scan.nextInt(); } int[][] columns = new int[columnCount + 1][]; for (int i = 1; i <= columnCount; i++) { int entriesCount = scan.nextInt(); columns[i] = new int[entriesCount + 1]; for (int j = 1; j <= entriesCount; j++) columns[i][j] = scan.nextInt(); } scan.close(); solve(rows, columns); } private static void solve(int[][] rowRunDescriptions, int[][] columnRunDescriptions) { // 1 = black, 0 = white, -1 = unknown // Store the board 1-based to align with the DP table int[][] board = new int[rowRunDescriptions.length][columnRunDescriptions.length]; for (int i = 1; i < rowRunDescriptions.length; i++) for (int j = 1; j < columnRunDescriptions.length; j++) board[i][j] = -1; // Repeatedly look for a row or column that gains more information from // the other available information. Stop when a steady state is reached. boolean changed = true; while (changed) { changed = false; for (int rowIndex = 1; rowIndex < rowRunDescriptions.length; rowIndex++) { // Store the square states 1-based to align with the DP table later int[] squares = new int[columnRunDescriptions.length]; for (int columnIndex = 1; columnIndex < columnRunDescriptions.length; columnIndex++) { squares[columnIndex] = board[rowIndex][columnIndex]; } if (tryUpdate(rowRunDescriptions[rowIndex], squares)) { changed = true; for (int i = 1; i < columnRunDescriptions.length; i++) { board[rowIndex][i] = squares[i]; } } } for (int columnIndex = 1; columnIndex < columnRunDescriptions.length; columnIndex++) { // Store the square states 1-based to align with the DP table later int[] squares = new int[rowRunDescriptions.length]; for (int rowIndex = 1; rowIndex < rowRunDescriptions.length; rowIndex++) { squares[rowIndex] = board[rowIndex][columnIndex]; } if (tryUpdate(columnRunDescriptions[columnIndex], squares)) { changed = true; for (int i = 1; i < rowRunDescriptions.length; i++) { board[i][columnIndex] = squares[i]; } } } } PrintResult(board); } private static boolean tryUpdate(int[] blockRunDescriptions, int[] squares) { // 1 = black, 0 = white, -1 = unknown // For each square that is not yet determined, try setting it to black // and white and check whether that new arrangement of squares is invalid. // If it's invalid, then we know the square must be the opposite color. boolean updated = false; for (int squareIndex = 1; squareIndex < squares.length; squareIndex++) { // The square may already be determined if (squares[squareIndex] != -1) continue; // Try making it black squares[squareIndex] = 1; if (!isLegal(blockRunDescriptions, squares)) { updated = true; squares[squareIndex] = 0; continue; } // Try making it white squares[squareIndex] = 0; if (!isLegal(blockRunDescriptions, squares)) { updated = true; squares[squareIndex] = 1; continue; } // No information gained. Reset to unknown. squares[squareIndex] = -1; } return updated; } // Determines whether the blockRunDescriptions are consistent with the given square states private static boolean isLegal(int[] blockRunDescriptions, int[] squares) { // 1 = black, 0 = white, -1 = unknown int n = squares.length - 1; int k = blockRunDescriptions.length - 1; // [i][j] is true iff all of the blocks in [i, j] are black or unknown boolean[][] allBlackOrUnknown = new boolean[n + 1][n + 1]; for (int i = 1; i <= n; i++) { allBlackOrUnknown[i][i] = squares[i] != 0; for (int j = i + 1; j <= n; j++) { allBlackOrUnknown[i][j] = allBlackOrUnknown[i][j - 1] && squares[j] != 0; } } allBlackOrUnknown[0][0] = true; for (int i = 1; i <= n; i++) { allBlackOrUnknown[0][i] = allBlackOrUnknown[1][i]; } // [i][j] is true iff all of the blocks in [i, j] are white or unknown boolean[][] allWhiteOrUnknown = new boolean[n + 1][n + 1]; allWhiteOrUnknown[0][0] = true; for (int i = 1; i <= n; i++) { allWhiteOrUnknown[i][i] = squares[i] != 1; for (int j = i + 1; j <= n; j++) { allWhiteOrUnknown[i][j] = allWhiteOrUnknown[i][j - 1] && squares[j] != 1; } } allWhiteOrUnknown[0][0] = true; for (int i = 1; i <= n; i++) { allWhiteOrUnknown[0][i] = allWhiteOrUnknown[1][i]; } boolean[][] memo = new boolean[n + 1][k + 1]; // Memo[i][j] indicates whether the first i squares [0, i - 1] can be satisfied by the first j block runs [0, j - 1] // Memo[n][k] will be our answer // Base cases (where i or j is 0): // Memo[0][0] = true // Memo[0][j] = false for j > 0 // Memo[i][0] = true if there are no black squares in the first i squares memo[0][0] = true; for (int i = 1; i <= n; i++) { if (squares[i] == 1) { break; } memo[i][0] = true; } for (int j = 1; j <= k; j++) { for (int i = 1; i <= n; i++) { // DP cases: considering positive number of squares up to index i - 1 and positive // number of block runs up to index j - 1. boolean valid = false; if (squares[i] != 1) { // If the square is (or could be) white, then we just care if the j block runs // satisfy the squares prior to this one. valid |= memo[i - 1][j]; } if (squares[i] != 0) { // If the square is (or could be) black, then there is a lot more to consider. // First, there must be enough room for block run j if (i >= blockRunDescriptions[j]) { // Second, there must be no known white cells in that run (which necessarily // ends at the current square) if (allBlackOrUnknown[i - blockRunDescriptions[j] + 1][i]) { // Special cases for only one run versus multiple runs if (j == 1) { // Since the run ends at the current square, we must validate that // nothing before the run is black valid |= i == blockRunDescriptions[j] || allWhiteOrUnknown[0][i - blockRunDescriptions[j]]; } else { // There are multiple runs. // 1. There has to be room for this run & at least one previous white cell // 2. The previous cell must be white // 3. The previous runs must be satisfied by the blocks before the forced white cell valid |= i > blockRunDescriptions[j] && squares[i - blockRunDescriptions[j]] != 1 && memo[i - blockRunDescriptions[j] - 1][j - 1]; } } } } memo[i][j] = valid; } } return memo[n][k]; } private static void PrintResult(int[][] board) { for (int r = 1; r < board.length; r++) { for (int c = 1; c < board[0].length; c++) { if (board[r][c] == 1) System.out.print("X"); else if (board[r][c] == 0) System.out.print("."); else System.out.print("?"); } System.out.println(); } } }