Saturday, April 12, 2014

Google Code Jam 2014 Qualification Round C Minesweeper Master (small input only)

// Google Code Jam 2014 Qualification Round C Minesweeper Master
// Problem: https://code.google.com/codejam/contest/2974486/dashboard#s=p2
import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;

//Google Code Jam
public class GoogleCode3 {
private static MyScanner in;
private static PrintStream out = System.out;
private static PrintStream sysout = System.out;
static int caseNum;

private static void solve() throws IOException
{
PreCompute();
int C = in.nextInt();
for (int i = 0; i < C; i++) {
caseNum = i + 1;
out.print("Case #" + caseNum + ":");
out.println();
solveCase();
}
}

private static void PreCompute() {
}

private static void solveCase() throws IOException {
int R = in.nextInt();
int C = in.nextInt();
int M = in.nextInt();
// out.println(String.format("debug: %d %d %d NM=%d",
// R, C, M, R * C - M));

int nonMines = (R * C) - M;

if (M == 0) {
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
if (i == 0 && j == 0)
out.print('c');
else
out.print('.');
}
out.println();
}
return;
}

if (nonMines == 1) {
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
if (i == 0 && j == 0)
out.print('c');
else
out.print('*');
}
out.println();
}
return;
}

if (C == 1) {
out.println('c');
for (int i = 0; i < nonMines - 1; i++) {
out.println('.');
}
for (int i = 0; i < M; i++) {
out.println('*');
}
return;
}

if (R == 1) {
out.print('c');
for (int i = 0; i < nonMines - 1; i++) {
out.print('.');
}
for (int i = 0; i < M; i++) {
out.print('*');
}
out.println();
return;
}

// R>1, C>1
char[][] board = new char[R][C];
boolean transform = false;
if (nonMines < 4) {
out.println("Impossible");
return;
}
else if (!isSquareNumber(nonMines))
{
if (R < C) {
transform = true;
int tmp = R;
R = C;
C = tmp;
board =
new char[R][C];
}

for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
board[i][j] = '.';
}
}
int ir = 0;
int ic = 0;
int cntM = 0;
while (true) {
if (ic == C) {
ir++;
ic = 0;
if (ir == R)
break;
}
if (cntM + 2 <= M && ic + 2 == C) {
board[ir][ic] = '*';
ic++;
board[ir][ic] = '*';
ic++;
cntM += 2;
}
else if (cntM + 2 <= M && ir + 2 == R) {
board[ir][ic] = '*';
board[ir + 1][ic] = '*';
ic++;
cntM += 2;
}
else if (cntM + 2 == M && ir + 2 == R - 1 && ic > 0) {
ir++;
ic = 0;
board[ir][ic] = '*';
board[ir + 1][ic] = '*';
ic++;
cntM += 2;
}
else if ((ir + 2 < R && ic + 2 < C)) {
board[ir][ic] = '*';
ic++;
cntM++;
}
else {
ic++;
}
if (cntM == M)
break;
}
if (cntM != M) {
out.println("Impossible");
return;
}
board[R - 1][C - 1] = 'c';
}
else {
// M is sqr number
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
board[i][j] = '*';
}
}
int sqrnm = (int) Math.sqrt(nonMines);
int minRC = Math.min(R, C);
if (minRC < sqrnm) {
out.println("Impossible");
return;
}

for (int ir = 0; ir < sqrnm; ir++) {
for (int ic = 0; ic < sqrnm; ic++) {
board[ir][ic] = '.';
}
}
board[0][0] = 'c';
}
// print board
if (!transform) {
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
out.print(board[i][j]);
}
out.println();
}
}
else {
for (int i = 0; i < C; i++) {
for (int j = 0; j < R; j++) {
out.print(board[j][i]);
}
out.println();
}
}
}

private static boolean isSquareNumber(int m) {
for (int i = 0; i < 50; i++) {
if (i * i == m)
return true;
}
return false;
}

public static void main(String[] args) throws IOException {
// helpers for input/output
boolean usingFileForIO = true;
if (usingFileForIO) {
// using input.txt and output.txt as I/O
in = new MyScanner("E:\\zin.txt");
out = new PrintStream("E:\\zout.txt");
}
else {
in = new MyScanner();
out = System.out;
}

solve();
}

// =====================================
static class MyScanner {
Scanner inp = null;

public MyScanner() throws IOException
{
inp = new Scanner(System.in);
}

public MyScanner(String inputFile) throws IOException {
inp = new Scanner(new FileInputStream(inputFile));
}

public int nextInt() throws IOException {
return inp.nextInt();
}

public long nextLong() throws IOException {
return inp.nextLong();
}

public double nextDouble() throws IOException {
return inp.nextDouble();
}

public String nextString() throws IOException {
return inp.next();
}

public String nextLine() throws IOException {
return inp.nextLine();
}
}

}

No comments:

Post a Comment