The content below was generated entirely by machine translation. Please verify its accuracy. If anything is unclear, consult the Chinese source version.

1: Understanding the Problem

Given an N×NN\times N region containing two types of points, J and B, add one J point (or do not add one; when adding, it cannot be placed where a B point already exists), and find the largest square consisting of J points.

2: Analysis

2.1: Summary

Because the data is small (N<100)(N<100), and one J edge determines the other two edges of a square, we can enumerate J edges and check them to find the largest square.

2.2: A Little Mathematics

Suppose points P1P_1 and P2P_2 determine a line, and the vertical coordinate of P1P_1 is always higher than that of P2P_2. We can draw the following figure:

How do we calculate the coordinates of P3P_3 and P4P_4?

By observation, the four triangles in the figure are congruent. We only need to calculate the lengths of the long and short legs of the triangle (or the two different perpendicular legs; in this special case, the long and short legs are arranged as in the figure), then add an offset to obtain the coordinates of P3P_3 and P4P_4.

Long leg of the triangle:

L△=b1−b2L_{\triangle}= b_1 - b_2

Short leg of the triangle:

S△=a1−a2S_{\triangle}= a_1 - a_2

From these two formulas, we obtain the coordinates:

P3=(a2+L△,b2−S△)P_3 = (a_2 + L_{\triangle}, b_2 - S_{\triangle})

P4=(a1+L△,b1−S△)P_4 = (a_1 + L_{\triangle}, b_1 - S_{\triangle})

In addition to the arrangement shown, the line P1P2P_1P_2 determines another square:

Again, we can obtain the coordinates of P5P_5 and P6P_6 using the preceding method. For P3P_3 and P4P_4, we added or subtracted the two different triangle-leg lengths (L△(L_{\triangle} and S△)S_{\triangle}) from an offset. By observation, applying the opposite operations to the offset gives P5P_5 and P6P_6:

P5=(a2−L△,b2+S△)P_5 = (a_2 - L_{\triangle}, b_2 + S_{\triangle})

P6=(a1−L△,b1+S△)P_6 = (a_1 - L_{\triangle}, b_1 + S_{\triangle})

Because we need the area of the square, calculate it as:

area=(a1−a2)2+(b1−b2)2\text{area} = (a_1 - a_2)^2 + (b_1 - b_2)^2

2.3: Program Idea

We can now obtain the coordinates of P3∼6P_{3\sim6}. Next, determine whether the two squares determined by one edge are valid.

Because we may freely place one J point, a square may contain only three existing J points. The additional J point must be placed at an unoccupied point.

Therefore, the square made of P1∼4P_{1\sim4} is valid when:

(P3∈JANDP4∉B) OR (P3∉BANDP4∈J)(P_3 \in \text{J} \quad \text{AND}\quad P_4 \notin \text{B})\ \text{OR}\ (P_3 \notin \text{B} \quad\text{AND}\quad P_4 \in \text{J})

Note: J denotes the set of J points, and B denotes the set of B points.

The square made of P1,2,5,6P_{1,2,5,6} is handled similarly.

3: Implementation and Improvements

3.1: First Attempt

After thinking of the approach, I quickly wrote the code, but two test points timed out.

Submission

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
#include <bits/stdc++.h>
using namespace std;
int mp[120][120];
#define debug false
struct node { int x, y; };
vector<node> jc; // Set of J points.
int n;
void input() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        char temps[110]; scanf("%s", temps);
        for (int j = 0; temps[j]; j++) {
            if (temps[j] == 'J') { mp[i][j] = 1; jc.push_back(node{i, j}); }
            else if (temps[j] == 'B') mp[i][j] = -1;
            else if (temps[j] == '*') mp[i][j] = 0;
        }
    }
}
int main() {
    input(); int ans = 0;
    for (auto t1 : jc) for (auto t2 : jc) {
        if (t1.x == t2.x && t1.y == t2.y) continue;
        node p3, p4; node p1 = t1, p2 = t2;
        if (p1.y < p2.y) swap(p1, p2);
        p3.x = p2.x + (p1.y - p2.y); p3.y = p2.y - (p1.x - p2.x);
        p4.x = p1.x + (p1.y - p2.y); p4.y = p1.y - (p1.x - p2.x);
        if (p3.x >= 0 && p3.y >= 0 && p4.x >= 0 && p4.y >= 0 && p3.x < n && p3.y < n && p4.x < n && p4.y < n)
            if ((mp[p3.x][p3.y] == 1 && mp[p4.x][p4.y] != -1) || (mp[p3.x][p3.y] != -1 && mp[p4.x][p4.y] == 1))
                ans = max(ans, (p1.y - t2.y) * (p1.y - p2.y) + (p1.x - p2.x) * (p1.x - p2.x));
        p3.x = p2.x - (p1.y - p2.y); p3.y = p2.y + (p1.x - p2.x);
        p4.x = p1.x - (p1.y - p2.y); p4.y = p1.y + (p1.x - p2.x);
        if (p3.x >= 0 && p3.y >= 0 && p4.x >= 0 && p4.y >= 0 && p3.x < n && p3.y < n && p4.x < n && p4.y < n)
            if ((mp[p3.x][p3.y] == 1 && mp[p4.x][p4.y] != -1) || (mp[p3.x][p3.y] != -1 && mp[p4.x][p4.y] == 1))
                ans = max(ans, (p1.y - t2.y) * (p1.y - t2.y) + (p1.x - p2.x) * (p1.x - p2.x));
    }
    printf("%d", ans); system("pause");
}

3.2: Second Attempt

The code performs a great deal of useless calculation. We assumed that P1P_1’s vertical coordinate is always higher than P2P_2’s, so the program contains a check to ensure that assumption:

1
if (p1.y < p2.y) { swap(p1, p2); }

We enumerate all J-point pairs with two loops, so each edge can be enumerated twice in reverse order. We can skip such cases directly:

1
if ((p1.x == p2.x && p1.y == p2.y) || (p1.y < p2.y)) continue;

After this, every point entering the square-validity checks satisfies our assumption, and duplicate computation is reduced.

Further analysis shows that the loop only checks square validity. If the area of a square found during enumeration is no larger than the current answer, there is no need to check it, so skip it directly:

1
if ((p1.x == p2.x && p1.y == p2.y) || (p1.y < p2.y) || (((p1.y - p2.y) * (p1.y - p2.y) + (p1.x - p2.x) * (p1.x - p2.x)) <= ans)) continue;

After this improvement, the solution is accepted:

Accepted submission

The complete code and comments are:

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
#include <bits/stdc++.h>
using namespace std;
int mp[120][120];
#define debug false
struct node { int x, y; };
vector<node> jc; // Set of J points.
int n;
void input() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        char temps[110]; scanf("%s", temps);
        for (int j = 0; temps[j]; j++) {
            if (temps[j] == 'J') { mp[i][j] = 1; jc.push_back(node{i, j}); }
            else if (temps[j] == 'B') mp[i][j] = -1;
            else if (temps[j] == '*') mp[i][j] = 0;
        }
    }
}
int main() {
    input(); int ans = 0; int cnt = 0;
    for (auto p1 : jc) {
        for (auto p2 : jc) { // Enumerate two points to enumerate edges.
            if ((p1.x == p2.x && p1.y == p2.y) || (p1.y < p2.y) || (((p1.y - p2.y) * (p1.y - p2.y) + (p1.x - p2.x) * (p1.x - p2.x)) <= ans)) {
                // Temporary area is no larger than the current answer.
                continue;
            }
            cnt++;
            node p3;
            p3.x = p2.x + (p1.y - p2.y); p3.y = p2.y - (p1.x - p2.x);
            node p4;
            p4.x = p1.x + (p1.y - p2.y); p4.y = p1.y - (p1.x - p2.x);
            if (p3.x >= 0 && p3.y >= 0 && p4.x >= 0 && p4.y >= 0 && p3.x < n && p3.y < n && p4.x < n && p4.y < n) // Check validity.
                if ((mp[p3.x][p3.y] == 1 && mp[p4.x][p4.y] != -1) || (mp[p3.x][p3.y] != -1 && mp[p4.x][p4.y] == 1))
                    ans = max(ans, (p1.y - p2.y) * (p1.y - p2.y) + (p1.x - p2.x) * (p1.x - p2.x));
            // The second square determined by the edge.
            p3.x = p2.x - (p1.y - p2.y); p3.y = p2.y + (p1.x - p2.x);
            p4.x = p1.x - (p1.y - p2.y); p4.y = p1.y + (p1.x - p2.x);
            if (p3.x >= 0 && p3.y >= 0 && p4.x >= 0 && p4.y >= 0 && p3.x < n && p3.y < n && p4.x < n && p4.y < n) // Check validity.
                if ((mp[p3.x][p3.y] == 1 && mp[p4.x][p4.y] != -1) || (mp[p3.x][p3.y] != -1 && mp[p4.x][p4.y] == 1))
                    ans = max(ans, (p1.y - p2.y) * (p1.y - p2.y) + (p1.x - p2.x) * (p1.x - p2.x));
        }
    }
    printf("%d\n", ans);
    if (debug) printf("%d", cnt);
    system("pause");
}