Saturday, December 3, 2011

SRM525

Level 1 Level 2 Level 3
Div 1 Level 1 Level 2 Level 3
Div 2 Level 1 Level 2 Level 3

Tutorials:

Rank: 186.

Solution

The same with Div2-Level1.

Solution

Just enumerate every possibility could happen.
I saw people used DP counting the number of 'o' in the rectangle to reduce the time consuming.

Source Code:

/**
* @author antonio081014
* @since Nov 29, 2011, 4:23:01 AM
*/
import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;
import java.awt.geom.*;

public class DropCoins {

public int getMinimum(String[] board, int K) {
int N = board.length;
int M = board[0].length();
int ret = Integer.MAX_VALUE;
for (int x = 0; x < N; x++) {
for (int y = 0; y < M; y++) {
for (int xx = x + 1; xx <= N; xx++) {
for (int yy = y + 1; yy <= M; yy++) {
int count = 0;
for (int i = x; i < xx; i++) {
for (int j = y; j < yy; j++) {
if (board[i].charAt(j) == 'o')
count++;
}
}
if (count == K) {
int sum = 2 * Math.min(x, N - xx)
+ Math.max(x, N - xx) + 2
* Math.min(y, M - yy) + Math.max(y, M - yy);
ret = Math.min(ret, sum);
}

}
}
}
}
if (ret == Integer.MAX_VALUE)
return -1;
return ret;
}
// <%:testing-code%>
}

Solution

Actually, I used the most dummy way to solve this. (DFS)
The easier way would be check if two cell vertical aligned are both Water.
My solution failed because I didn't check the boundary before I go further.

Source Code:

/**
* @author antonio081014
* @since Nov 29, 2011, 4:02:41 AM
*/
import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;
import java.awt.geom.*;

public int N;

boolean[][] mark = new boolean[2][N];
return "YES";
else
return "NO";
}

public boolean search(boolean[][] mark, int x, int y, String[] road) {
if (x == 0 && y == N - 1)
return true;
if (y >= N)
return false;
mark[x][y] = true;
boolean ret = false;
int xx = 1 - x;
if (road[xx].charAt(y) != 'W' && !mark[xx][y])
ret = ret || search(mark, xx, y, road);
if (y + 1 < N && road[x].charAt(y + 1) != 'W' && !mark[x][y + 1])
ret = ret || search(mark, x, y + 1, road);
if (y + 1 < N && road[xx].charAt(y + 1) != 'W' && !mark[xx][y + 1])
ret = ret || search(mark, xx, y + 1, road);
return ret;
}

// <%:testing-code%>
}