Tävlingsprogrammering/Uppgifter/Miniröj

Uppgift

https://po.scrool.se/problems/miniroj

Lösning

Delpoäng

Det man kan notera i delpoängsuppgiften är att om vi fixerar den första cellen i övre raden (tillfälligt antar att den innehåller en mina eller att den är tom) så kommer innehållet i de övriga cellerna att vara entydigt bestämt. Vi har alltså högst två olika giltiga bräden, och att ta fram dem går att göra i linjär tid på följande sätt:

Loopa igenom cellerna i den nedre raden och räkna ut hur många minor som finns på dess sidor samt rakt ovanför och snett upp till vänster (dessa har vi redan bestämt när vi kommer hit). Om detta är lika med talet som står i cellen så finns ingen mina i cellen uppe till höger. Om antalet är ett mindre än det som står i cellen så måste det vara en mina i cellen uppe till höger. I alla andra fall så har vi stött på ett fel och vi markerar detta på något sätt.

Om det blir fel både när vi sätter en mina i den första cellen och när vi lämnar den tom så ska svaret vara 'fel'. I annat fall så har vi ett eller två giltiga bräden och vi kan ta fram svaret för varje cell utifrån dessa (detta kan ni nog lista ut hur man gör).

Full poäng

Att få 100 poäng på den här uppgiften är faktiskt inte så mycket svårare. Den enda skillnaden är att vi kan ha minor i den nedre raden, vilket gör att vi inte vet hur många minor som finns i närheten av dessa celler. Varje gång vi stöter på en sådan här cell behöver vi därför testa både att ha en mina i cellen uppe till höger och att lämna den tom. Det enklaste sättet att implementera detta på är med en dfs eller dynamisk programmering (där ett tillstånd består av positionen i nedre raden samt information om hur cellerna rakt ovanför och uppe till vänster ser ut).

Lösning i Java:

import java.io.*;
import java.util.*;

public class Miniroj {
	
	static final int MINE = -1;
	static final int NOT_VISITED = -2;
	static final int POSSIBLE = 1;
	static final int IMPOSSIBLE = 0;
	
	static final char MINE_CHAR = 'X';
	static final char UNKNOWN_CHAR = 'O';
	static final char SAFE_CHAR = 'S';
	
	static int N;
	static int[] cells;
	static int[][][] dp;
	
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter out = new PrintWriter(System.out);
		String s = in.readLine();
		
		N = s.length();
		cells = new int[N];
		for (int i = 0; i < N; i++) {
			cells[i] = s.charAt(i) == 'X' ? MINE : s.charAt(i) - '0';
		}
		dp = new int[N][2][2];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < 2; j++) {
				Arrays.fill(dp[i][j], NOT_VISITED);
			}
		}
		
		int solution = solve(0, 0, 0) | solve(0, 0, 1);
		if (solution == 0) {
			out.println("fel");
		} else {
			for (int i = 0; i < N; i++) {
				boolean mine = dp[i][0][1] == POSSIBLE || dp[i][1][1] == POSSIBLE;
				boolean safe = dp[i][0][0] == POSSIBLE || dp[i][1][0] == POSSIBLE;
				if (mine && safe) {
					out.write(UNKNOWN_CHAR);
				} else if (mine) {
					out.write(MINE_CHAR);
				} else {
					out.write(SAFE_CHAR);
				}
			}
			out.write('\n');
		}
		in.close();
		out.close();
	}
	
	static int solve(int pos, int topLeft, int topMid) {
		if (dp[pos][topLeft][topMid] != NOT_VISITED) return dp[pos][topLeft][topMid];
		int cnt = topLeft + topMid;
		if (pos > 0 && cells[pos - 1] == MINE) cnt++; // Mine to the left?
		if (pos < N - 1 && cells[pos + 1] == MINE) cnt++; // Mine to the right?
		int res = IMPOSSIBLE;
		if (pos == N - 1) {
			// We have reached the end. Check if the last cell is correct
			res = cells[pos] == MINE || cells[pos] == cnt ? POSSIBLE : IMPOSSIBLE;
		} else {
			// Try both putting a mine in the top right and leave it empty
			for (int topRight = 0; topRight < 2; topRight++) {
				if (cells[pos] == MINE || cells[pos] == cnt + topRight) {
					if (solve(pos + 1, topMid, topRight) == POSSIBLE) res = POSSIBLE;
				}
			}
		}
		return dp[pos][topLeft][topMid] = res;
	}
}