解題區►解題區 - UVa

UVa 12812 - The Largest Diamond-Shaped Kite

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

找一個最大箏形於給定的地圖中。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3 3
.#.
###
.#.
8 10
..##...#..
.###..###.
..#.......
....##....
....######
...#####..
..########
.....#....

Sample Output

1
2
3
5

Solution

其實很像找一個最大正方形，可以參考 NPSC 營地的作法。而要求箏形事實上就是將地圖翻轉 45 度角。

參考 UVa 10593 - Kites 的做法可以完成。

以前寫的 代碼 真是萌哒。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <string.h>
#include <assert.h>
#include <map>
using namespace std;
char g[512][512];
int dp[512][512];
int main() {
    int testcase;
    int n, m;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        for (int i = 0; i < n; i++) {
            scanf("%s", g[i]);
        }
        int ret = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (g[i][j] == '#') {
                    int v1, v2, v3;
                    v1 = i-1 >= 0 && j-1 >= 0 ? dp[i-1][j-1] : 0;
                    v2 = i-2 >= 0 ? dp[i-2][j] : 0;
                    v3 = i-1 >= 0 && j+1 < m ? dp[i-1][j+1] : 0;
                    if (i-1 >= 0 && g[i-1][j] == '#')
                        dp[i][j] = min(v1, min(v2, v3)) + 1;
                    else
                        dp[i][j] = 1;
                } else {
                    dp[i][j] = 0;
                }
                ret = max(ret, dp[i][j]);
            }
        }
        printf("%d\n", ret * 2 - 1 < 0 ? 0 : ret * 2 - 1);
    }
    return 0;
}
/*
 2
 3 3
 .#.
 ###
 .#.
 8 10
 ..##...#..
 .###..###.
 ..#.......
 ....##....
 ....######
 ...#####..
 ..########
 .....#....
 */