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);
}