import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; import java.util.Map.Entry; import java.util.Scanner; public class prog { public static void main(String[] args) throws java.lang.Exception { //long start = System.currentTimeMillis(); Scanner scanner = new Scanner(System.in); Integer type = Integer.parseInt(scanner.nextLine()); String[] data = scanner.nextLine().split(" "); Integer m = Integer.parseInt(data[0]); Integer n = Integer.parseInt(data[1]); char[][] matrix = new char[m][n]; List margins = new ArrayList(); WeightedQuickUnionUF uf = new WeightedQuickUnionUF(n * m); for (int i = 0; i < m; i++) { String cells = scanner.nextLine(); for (int j = 0; j < cells.length(); j++) { matrix[i][j] = cells.charAt(j); } } for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { int similarNeighbors = 0; int coord = get1DCoord(i, j, n); if (i > 0) { if (matrix[i][j] == matrix[i - 1][j]) { if (!uf.connected(coord, (i - 1) * n + j)) { uf.union(coord, (i - 1) * n + j); } similarNeighbors++; } } else { similarNeighbors++; } if (j > 0) { if (matrix[i][j] == matrix[i][j - 1]) { if (!uf.connected(coord, i * n + j - 1)) { uf.union(coord, i * n + j - 1); } similarNeighbors++; } } else { similarNeighbors++; } if (i < m - 1) { if (matrix[i][j] == matrix[i + 1][j]) { if (!uf.connected(coord, (i + 1) * n + j)) { uf.union(coord, (i + 1) * n + j); } similarNeighbors++; } } else { similarNeighbors++; } if (j < n - 1) { if (matrix[i][j] == matrix[i][j + 1]) { if (!uf.connected(coord, i * n + j + 1)) { uf.union(coord, i * n + j + 1); } similarNeighbors++; } } else { similarNeighbors++; } if (similarNeighbors < 4) { margins.add(get1DCoord(i, j, n)); } } } int maxSize = uf.getMaxSize(); if (type == 1) { System.out.print(maxSize); } else { if (maxSize == n * m) { System.out.println(1 + " " + 1); System.out.print(matrix[0][0]); } else { int x = 0; int y = 0; int xLastResort = -1; int yLastResort = 0; char ch = 'a'; char chLastResort = 'a'; for (int k = 0; k < margins.size(); k++) { Integer margin = margins.get(k); int[] coord2D = get2DCoord(margin, m, n); Map matchingNeighboursFrequency = new HashMap(); Map> matchingNeighbours = new HashMap>(); char currentChar = matrix[coord2D[0]][coord2D[1]]; if (coord2D[0] > 0) { processNeighbor(n, matrix, new int[] { coord2D[0]-1, coord2D[1] }, matchingNeighboursFrequency, matchingNeighbours, currentChar); } if (coord2D[1] > 0) { processNeighbor(n, matrix, new int[] { coord2D[0], coord2D[1] - 1 }, matchingNeighboursFrequency, matchingNeighbours, currentChar); } if (coord2D[0] < m - 1) { processNeighbor(n, matrix, new int[] { coord2D[0] + 1, coord2D[1] }, matchingNeighboursFrequency, matchingNeighbours, currentChar); } if (coord2D[1] < n - 1) { processNeighbor(n, matrix, new int[] { coord2D[0], coord2D[1] + 1 }, matchingNeighboursFrequency, matchingNeighbours, currentChar); } for (Entry entry : matchingNeighboursFrequency.entrySet()) { Character key = entry.getKey(); Integer value = entry.getValue(); if (xLastResort == -1) { int[] coord2DLS = get2DCoord(matchingNeighbours.get(key).get(0), m, n); xLastResort = coord2DLS[0]; yLastResort = coord2DLS[1]; chLastResort = key; } if (value > 1) { List nList = matchingNeighbours.get(key); int size = 0; for (int i = 0; i < nList.size(); i++) { if (i == 0) { size += uf.getSize(nList.get(i)); } for (int j = 0; j < i; j++) { if (!uf.connected(nList.get(i), nList.get(j))) { size += uf.getSize(nList.get(i)); } } } if (maxSize < size) { maxSize = Math.max(maxSize, size); ch = key; x = coord2D[0]; y = coord2D[1]; } } } } if (maxSize != uf.getMaxSize()) { System.out.println((x + 1) + " " + (y + 1)); System.out.println(ch); } else { System.out.println((xLastResort + 1) + " " + (yLastResort + 1)); System.out.println(chLastResort); } } } scanner.close(); //System.out.println("Ms: "+(System.currentTimeMillis()-start)/1000); } private static void processNeighbor(Integer n, char[][] matrix, int[] coord2D, Map matchingNeighboursFrequency, Map> matchingNeighbours, char currentChar) { char nChar = matrix[coord2D[0]][coord2D[1]]; if (currentChar != nChar) { addToFrequencyMap(matchingNeighboursFrequency, nChar); addToMap(matchingNeighbours, nChar, get1DCoord(coord2D[0], coord2D[1], n)); } } private static void addToFrequencyMap(Map matchingNeighboursFrequency, char c) { if (matchingNeighboursFrequency.containsKey(c)) { matchingNeighboursFrequency.put(c, matchingNeighboursFrequency.get(c) + 1); } else { matchingNeighboursFrequency.put(c, 1); } } private static void addToMap(Map> matchingNeighbours, char c, int coord) { List list; if (matchingNeighbours.containsKey(c)) { list = matchingNeighbours.get(c); list.add(coord); } else { list = new ArrayList(); list.add(coord); matchingNeighbours.put(c, list); } } private static int[] get2DCoord(int coord, int m, int n) { return new int[] { coord / n, coord % n }; } private static int get1DCoord(int i, int j, int n) { return i * n + j; } public static class WeightedQuickUnionUF { private int[] parent; private int[] size; private int count; private int maxSize; public WeightedQuickUnionUF(int N) { count = N; parent = new int[N]; size = new int[N]; maxSize = 1; for (int i = 0; i < N; i++) { parent[i] = i; size[i] = 1; } } public int find(int p) { while (p != parent[p]) { p = parent[p]; } return p; } public int count() { return count; } public boolean connected(int p, int q) { return find(p) == find(q); } public int getMaxSize() { return maxSize; } public int getSize(int p) { return size[find(p)]; } public void union(int p, int q) { int rootP = find(p); int rootQ = find(q); if (rootP != rootQ) { if (size[rootP] < size[rootQ]) { parent[rootP] = rootQ; size[rootQ] += size[rootP]; maxSize = Math.max(maxSize, size[rootQ]); } else { parent[rootQ] = rootP; size[rootP] += size[rootQ]; maxSize = Math.max(maxSize, size[rootP]); } count--; } } } }