Algoogle

Algorithm for Programming Contest

PKU 3251 Big Square

Category: PKU Tag: implementation

Big Square

問題概要


解法


‘J’ の場所を2個選んでそれを1辺とする正方形2個を作ってみてできるなら答えとmax取る.
O(N^4)になるが実際には現在の最高値と2点の距離で大量に簡単に枝刈りできるので割りと余裕.

コード


(3251.cpp) download
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
#include <cstdio>
#include <vector>
#include <map>

using namespace std;

typedef pair<int,int> pii;

int N;
char table[128][128];
vector<pii> Js;

inline bool in(int i, int j){ return i >= 0 && j >= 0 && i < N && j < N;}
inline bool in(pii a){ return in(a.first, a.second);}
inline int f(pii a){ return int(table[a.first][a.second]);}

int main(){
    scanf("%d", &N);
    for(int i = 0; i < N; i++){
        scanf("%c", &table[i][N]);
        for(int j = 0; j < N; j++){
            scanf("%c", &table[i][j]);
            if(table[i][j] == 'J') Js.push_back(pii(i,j));
        }
    }
    int ans = 0;
    for(int i = 0; i < Js.size(); i++)
        for(int j = i+1; j < Js.size(); j++){
            pii a = Js[i], b = Js[j];
            int di = b.first - a.first, dj = b.second - a.second;
            if(ans >= di*di+dj*dj) continue;
            pii c = pii(a.first - dj, a.second + di);
            pii d = pii(c.first + di, c.second + dj);
            if(in(c) && in(d) && ((f(c)+f(d) == int('J'+'*')) || (f(c)+f(d) == int('J'+'J')))){
                ans = di*di+dj*dj;
                //                printf("(%d, %d) (%d, %d) (%d, %d) (%d, %d) -> %d\n", a.first, a.second, b.first, b.second, c.first, c.second, d.first, d.second, ans);
                continue;
            }
            c = pii(a.first + dj, a.second - di);
            d = pii(c.first + di, c.second + dj);
            if(in(c) && in(d) && ((f(c)+f(d) == int('J'+'*')) || (f(c)+f(d) == int('J'+'J')))){
                ans = di*di+dj*dj;
                //                printf("(%d, %d) (%d, %d) (%d, %d) (%d, %d) -> %d\n", a.first, a.second, b.first, b.second, c.first, c.second, d.first, d.second, ans);
                continue;
            }
        }
    printf("%d\n", ans);
    return 0;
}

Comments