The easy solution (Marius Gavrilescu)

We will use a flood fill function that computes the area of a zone.

For the first kind of queries we will call the function for each cell and print the largest value returned by the function.

For the second kind of queries, if we change the color of a cell, we should change it to the color of one of its neighbours (otherwise it does not increase the area of a region). Thus, for each cell we can take each of its neighours, change the color of the cell to that of the neighbour and call our fill function.

    1 #include<stdio.h>
    2 const int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
    3 
    4 char v[405][405];
    5 int us[405][405], filln = 1;
    6 
    7 int fill(int x, int y, int c){
    8     int ans = 1;
    9     us[x][y] = filln;
   10     for(int i = 0; i < 4; i++){
   11         int nx = x + dx[i], ny = y + dy[i];
   12         if(v[nx][ny] == c && us[nx][ny] < filln)
   13             ans += fill(nx, ny, c);
   14     }
   15     return ans;
   16 }
   17 
   18 int main(void){
   19     int t, m, n;
   20     scanf("%d%d%d ", &t, &m, &n);
   21     for(int i = 1; i <= m; i++)
   22         scanf("%s ", &v[i][1]);
   23 
   24     int best = 0, bestx, besty, cur;
   25     char bestc;
   26     for(int x = 1; x <= m; x++)
   27         for(int y = 1; y <= n; y++){
   28             cur = fill(x, y, v[x][y]);
   29             if(cur > best)
   30                 best = cur, bestx = x, besty = y, bestc = v[x][y];
   31             if(t == 1)
   32                 continue;
   33             for(int k = 0; k < 4; k++){
   34                 int nx = x + dx[k], ny = y + dy[k];
   35                 if(!v[nx][ny] || v[nx][ny] == v[x][y])
   36                     continue;
   37                 cur = fill(x, y, v[nx][ny]);
   38                 filln++;
   39                 if(cur > best)
   40                     best = cur, bestx = x, besty = y, bestc = v[nx][ny];
   41             }
   42         }
   43 
   44     if(t == 1)
   45         printf("%d\n", best);
   46     else
   47         printf("%d %d\n%c\n", bestx, besty, bestc);
   48     return 0;
   49 }

The fast solution (Gabriel Inelus)

A more efficient way of solving the type 2 queries is the following:

First of all we should define some helping structures:

• Let a component be the maximal region of the same colour. A position (x,y) is a member of the component C if and only if Fill(x,y) denotes the full component C.
• Let quant be an array which contains the area of a specific component.
• Let used mean both that the coordinate (x,y) has been visited and also used[x][y] means to which component does (x,y) belong.

Then, we can use these structures as follows: quant[used[x][y]] is the area of the component that (x,y) belongs to.

To answer the type 2 query, we must scan the matrix and for each (x,y) we should test the relevant characters (only the ones of the 4 neighbours) and use the quant vector to calculate the new area.

The complexity of this algorithm is O(N*M*K) where K = 16 (for every position we choose 4 neighbours and 4 colours)