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.

---

Division One - Level Three:

Solution

Source Code:

---

Division One - Level Two:

Solution

Source Code:

---

Division One - Level One:

Solution

The same with Div2-Level1.

Source Code:

---

Sivision Two - Level Three:

Solution

Source Code:

---

Division Two - Level Two:

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%>
}
// Powered by [KawigiEdit] 2.0!

---

Division Two - Level One:

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 class RainyRoad {
    public int N;

    public String isReachable(String[] road) {
        N = road[0].length();
        boolean[][] mark = new boolean[2][N];
        if (search(mark, 0, 0, road))
            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%>
}
// Powered by [KawigiEdit] 2.0!