URAL 1221. Malevich Strikes Back!

Author: 2015-10-09

ACM

, ,

1. 题目

http://acm.timus.ru/problem.aspx?space=1&num=1221

1221. Malevich Strikes Back!

Time limit: 1.0 second
Memory limit: 64 MB

Problem illustration

After the greatest success of Malevich’s “Black Square” the famous artist decided to create a new masterpiece. He took a large sheet of checked paper and filled some cells with black. After that he realized the picture to be too complicated. He was afraid, that people would not understand the sense of the painting. Thus, Malevich decided to cut out a smaller picture of the special form. It should be a black square with its sides parallel to the sides of the list. A white square rotated by 45 degrees should be placed inside the black square. The corners of the white square should lay on the sides of the black square. You can see an example of such picture on the figure.
The original paper size is N × N, 0 < N ≤ 100. Your program should help Malevich to find the largest figure corresponding to the pattern described above.

Input

The input contains several test cases. Each test case starts with the size of paper N. The following N lines of the test case describe the original painting: “1” denotes a black and “0” denotes a white cell. End of the input is marked by a zero value for N.

Output

Your program should output the size (i.e. the maximum width or height) of the largest figure, which Malevich would like to cut out. If no such figure exists, output “No solution”.

Sample

input output 
6
1 1 0 1 1 0
1 0 0 0 1 1
0 0 0 0 0 0
1 0 0 0 1 1
1 1 0 1 1 1 
0 1 1 1 1 1
4
1 0 0 1
0 0 0 0
0 0 0 0
1 0 0 1
0
 
5
No solution
Problem Author: Nikita Shamgunov
Problem Source: The Seventh Ural State University collegiate programming contest

2. 思路

寻找符合所给图样的最大图块。

N最大只有100，暴力搜索即可。也可先DP一下，记录连续白块和黑块的数量，简化搜索。

3. 代码

#include <cstdio>

const int MAX_N = 101;

typedef int Graph[MAX_N][MAX_N];

void solveE7e_MalevichStrikesBack();
int input(Graph g);
int size(Graph g, int n, int row, int col, int height);

int main() {
    // freopen("test.txt", "r", stdin);
    solveE7e_MalevichStrikesBack();
    return 0;
}

Graph g, wCnt, bCnt;
void solveE7e_MalevichStrikesBack() {
    int n = input(g);

    while (n != 0) {
        int result = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                //printf("%d %d\n", i, j);
                if (g[i][j] == 0 && g[i][j - 1] == 1 && g[i][j + 1] == 1) {
                    int height = 0;
                    for (height = i + 1; height <= n; ++height) {
                        if (g[height][j] == 0 && g[height][j - 1] == 1 && g[height][j + 1] == 1)
                            break;
                    }
                    height = height - i + 1;
                    if (height >= 3) {
                        int currSize = size(g, n, i, j, height);
                        result = result > currSize ? result : currSize;
                    }
                }
            }
        }
        if (result) {
            printf("%d\n", result);
        } else {
            printf("No solution\n");
        }
        
        n = input(g);
    }
}

int input(Graph g) {
    int n;
    scanf("%d", &n);

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            scanf("%d", &g[i][j]);
        }
    }

    return n;
}

int size(Graph g, int n, int row, int col, int height) {
    for (int i = 0; i <= height/2; ++i) {
        for (int j = 0; j <= i; ++j) {
            if ((col + j) > n || (col - j) < 0 || g[row + i][col + j] != 0 || g[row + i][col - j] != 0) {
                return 0;
            }
            if (g[row + height - 1 - i][col + j] != 0 || g[row + height - 1 - i][col - j] != 0) {
                return 0;
            }
        }
        for (int j = i + 1; j <= height/2; ++j) {
            if ((col + j) > n || (col - j) < 0 || g[row + i][col + j] != 1 || g[row + i][col - j] != 1) {
                return 0;
            }
            if (g[row + height - 1 - i][col + j] != 1 || g[row + height - 1 - i][col - j] != 1) {
                return 0;
            }
        }
    }
    return height;
}