填图游戏

SRM444DIV1 550分

 

大概意思是给定一个一定长宽的表，现在手中有两种卡片一种是2*2的“4”字卡片（16分），另一种是1*1的“1”字卡片（1分），卡片数不限，计算可以将其填入表中得到的最大分，图表中可能已有卡片存在。

*Problem Statement
NOTE: This problem statement contains images that may not display properly if viewed outside of the applet.

 

"4Blocks" is a two player cooperative game played on a special board. The board is a grid composed of 1x1 square cells. There are two different kinds of blocks: '1' blocks and '4' blocks. '1' blocks are 1x1, and '4' blocks are 2x2:

 

 

 

You must place blocks on the board so that their sides are aligned to the grid lines and no two blocks overlap. The final score is the sum of the values in each cell. '1' blocks are worth 1 point, and '4' blocks are worth 16 points because they cover 4 cells and each cell is worth 4 points.

 

Your friend has taken his turn and placed a number of '1' blocks on the board. The current configuration is given in the String[] grid. The j-th character of the i-th element of grid is '.' if the cell at row i, column j is empty, and '1' if your friend placed a '1' block in that cell. It is now your turn, and you can place any number of '1' or '4' blocks on the board, but you cannot remove any of the blocks that have already been placed. Return the maximum score that can be achieved. For example, the following images show one possible starting state, and the optimal placement of blocks from that state:

 

 

 

The final score would be 4*16 + 6*1 = 70.

Definition
Class: FourBlocks
Method: maxScore
Parameters: String[]
Returns: int
Method signature: int maxScore(String[] grid)
(be sure your method is public)

 

Constraints
- grid will contain between 1 and 10 elements, inclusive.
- Each element of grid will contain between 1 and 25 characters, inclusive.
- All elements of grid will contain the same number of characters.
- Each element of grid will contain only '.' or '1' (one).

Examples
0)
{".....1..1..",
"..1.....1.."}

Returns: 70

This is the example from the statement.

1)
{"...1.",
".....",
".1..1",
".....",
"1...."}

Returns: 73

 

2)
{"...1.",
".1...",
"..1.1",
"1...."}

Returns: 20

It is not possible to place any '4' bricks in this setup.

3)
{".....1...",
".....1...",
"111111111",
".....1...",
".....1..."}

Returns: 117

 

发现最做Topcoder有个老是习惯先浏览一下其他人的算法，大概心里有数。这道题刚开始看时确实有点吓到，列位大牛写的东西几乎看不懂，还用到了位运算，有的就用三维数组，真是云里雾里。

不过自己尝试一下发现不是那么回事，一气写下来就调了一个bug,算了一下复杂度照其他来说还是比较低的。

可见有时候还是应该相信自己多一点。算法如下：

public class FourBlocks {

    /**
     * @param args the command line arguments
     */
    public static int maxScore(String[] grid) {
        int result = 0;
        int wid = grid[0].length();
        int len = grid.length;
//        int s = (1<< wid);//2的w次方
        int[][] check = new int[len + 1][wid + 1];
        int count4 = 0;
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < wid; j++) {
                check[i][j] = -1;
            }
        }

        for (int i = 0; i < len; i++) {
            for (int j = 0; j < wid; j++) {
                if ((i + 1) < len && j + 1 < wid) {
                    char c00 = grid[i].charAt(j);
                    char c01 = grid[i].charAt(j + 1);
                    char c10 = grid[i + 1].charAt(j);
                    char c11 = grid[i + 1].charAt(j + 1);
                    if (check[i][j] != 1 && c00 == '.' && c10 == '.' && c01 == '.' && c11 == '.') {
                        count4++;
                        check[i][j] = check[i][j + 1] = check[i + 1][j] = check[i + 1][j + 1] = 1;
                    }
                }
            }
        }
        result = 12 * count4 + wid * len;
//        {
//            System.out.println(s);
//        }

        return result;
    }

    public static void main(String[] args) {
        // TODO code application logic here
        String[] grid = {".....1...",
            ".....1...",
            "111111111",
            ".....1...",
            ".....1..."};
        System.out.println(maxScore(grid));
    }
}