Untitled
unknown
plain_text
a month ago
2.5 kB
1
Indexable
Never
import java.util.Scanner; public class StoneGame { private static final char WHITE = 'w'; private static final char BLACK = 'b'; public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int testCaseCount = scanner.nextInt(); for (int testCaseNumber = 1; testCaseNumber <= testCaseCount; testCaseNumber++) { char[][] board = new char[4][4]; for (int row = 0; row < 4; row++) { String line = scanner.next(); for (int col = 0; col < 4; col++) { board[row][col] = line.charAt(col); } } int minimumOperationCount = Integer.MAX_VALUE; backtrack(board, 0, 0, 0, 0, minimumOperationCount); if (minimumOperationCount == Integer.MAX_VALUE) { System.out.println("Case #" + testCaseNumber + " impossible"); } else { System.out.println("Case #" + testCaseNumber + " " + minimumOperationCount); } } scanner.close(); } private static void backtrack(char[][] board, int row, int col, int whiteCount, int blackCount, int minimumOperationCount) { if (row == 4) { if (whiteCount == 0 || blackCount == 0) { minimumOperationCount = Math.min(minimumOperationCount, Math.max(whiteCount, blackCount)); } return; } if (minimumOperationCount <= Math.max(whiteCount, blackCount)) { return; } for (int rowOffset = -1; rowOffset <= 1; rowOffset++) { for (int colOffset = -1; colOffset <= 1; colOffset++) { if (rowOffset == 0 && colOffset == 0) { continue; } int newRow = row + rowOffset; int newCol = col + colOffset; if (isValidCell(board, newRow, newCol)) { board[row][col] = board[newRow][newCol] == WHITE ? BLACK : WHITE; backtrack(board, newRow, newCol, whiteCount + (board[row][col] == WHITE ? 1 : -1), blackCount + (board[row][col] == BLACK ? 1 : -1), minimumOperationCount); board[row][col] = board[newRow][newCol] == WHITE ? BLACK : WHITE; // Restore original value } } } } private static boolean isValidCell(char[][] board, int row, int col) { return 0 <= row && row < 4 && 0 <= col && col < 4; } }