Solution Notes: This is a relatively straightforward shortest path problem, where we want to compute the so-called "diameter" of a graph (the longest shortest path) by finding the shortest path from every node to every other node (here, each location in the grid is a node, and the cost of moving from one node to another is either A or B, dependng on whether the corresponding parentheses match or not).
The simplest algorithm for solving the all-pairs shortest path problem is probably the Floyd-Warshall algorithm. However, since this runs in O(n^3) time and here n = 40*40, it is not quite fast enough. Instead, we choose to run n instances of Dijkstra's single-source shortest path algorithm, one for each source node in the graph. If we use a heap to store distance labels, this runs in O(n^2 log n) time, which is fast enough to solve all input cases.
Solution code from Travis Hance is shown below:
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
#define NMAX 40
int grid[NMAX][NMAX];
struct node {
int i, j;
int dist;
node(int i, int j, int dist) : i(i), j(j), dist(dist) { }
bool operator<(node const& other) const {
return dist > other.dist;
}
};
int di[] = {1,-1,0,0};
int dj[] = {0,0,1,-1};
bool visited[NMAX][NMAX];
int getRadius(int n, int sourcei, int sourcej, int costSame, int costDiff) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
visited[i][j] = false;
}
}
priority_queue<node> q;
q.push(node(sourcei, sourcej, 0));
int maxDist = 0;
while (q.size() > 0) {
node v = q.top();
q.pop();
if (!visited[v.i][v.j]) {
visited[v.i][v.j] = true;
for (int d = 0; d < 4; d++) {
int i1 = v.i + di[d];
int j1 = v.j + dj[d];
if (i1 >= 0 && i1 < n && j1 >= 0 && j1 < n) {
int dist = v.dist + (grid[v.i][v.j] == grid[i1][j1] ? costSame : costDiff);
q.push(node(i1, j1, dist));
}
}
maxDist = max(maxDist, v.dist);
}
}
return maxDist;
}
int main() {
freopen("distant.in","r",stdin);
freopen("distant.out","w",stdout);
int n, costSame, costDiff;
scanf("%d", &n);
scanf("%d", &costSame);
scanf("%d", &costDiff);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
char c;
do { c = fgetc(stdin); } while (c != '(' && c != ')');
grid[i][j] = c;
}
}
int diam = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int radius = getRadius(n, i, j, costSame, costDiff);
diam = max(diam, radius);
}
}
printf("%d\n", diam);
}