UVA10908

4th IIUC Inter-University Programming Contest, 2005
D	Largest Square
	Input: standard inputOutput: standard output
	Problemsetter: Tanveer Ahsan

Given a rectangular grid of characters you have to find out the length of a side of the largest square such that all the characters of the square are same and the center [intersecting point of the two diagonals] of the square is at location (r, c). The height and width of the grid is M and N respectively. Upper left corner and lower right corner of the grid will be denoted by (0, 0) and (M-1, N-1)respectively. Consider the grid of characters given below. Given the location (1, 2) the length of a side of the largest square is 3.

abbbaaaaaaabbbaaaaaaabbbaaaaaaaaaaaaaaaaaaaaaaaaaaaaccaaaaaaaaccaaaaaa

Input

The input starts with a line containing a single integer T (< 21). This is followed by T test cases. The first line of each of them will contain three integers M, N and Q (< 21) separated by a space where M, N denotes the dimension of the grid. Next follows M lines each containing N characters. Finally, there will be Q lines each containing two integers r and c. The value of M and N will be at most100.

Output

For each test case in the input produce Q+1 lines of output. In the first line print the value of M, N and Q in that order separated by single space. In the next Q lines, output the length of a side of the largest square in the corresponding grid for each (r, c) pair in the input.

Sample Input	Output for Sample Input
1 7 10 4 abbbaaaaaa abbbaaaaaa abbbaaaaaa aaaaaaaaaa aaaaaaaaaa aaccaaaaaa aaccaaaaaa 1 2 2 4 4 65 2	7 10 43151

解法:模擬 以給的點左上角開始爆搜，每搜完沒有點是不相同的大小就+2 or DP

import java.util.Scanner;

public class UVA10908 {

 public static void main(String[] args) {

  Scanner sc = new Scanner(System.in);

  int count = Integer.parseInt(sc.nextLine());

  for (int k = 0; k < count; k++) {

   int row = sc.nextInt();
   int col = sc.nextInt();
   int num = sc.nextInt();

   sc.nextLine();

   System.out.println(row + " " + col + " " + num);

   if(row==0 || col==0 || num==0){

    continue;

   }

   char matrix[][] = new char[row][col];

   for (int i = 0; i < row; i++) {

    String s2 = sc.nextLine();

    for (int j = 0; j < col; j++)
     matrix[i][j] = s2.charAt(j);

   }

   for (int n = 0; n < num; n++) {

    int size = 1, constant = 1;

    boolean check = true;

    int specify_x = sc.nextInt();

    int specify_y = sc.nextInt();

    if(specify_x>row-1 || specify_y>col-1)
    {
     System.out.println(0);
     continue;
    }

    char chr = matrix[specify_x][specify_y];

    while (check) {

     for (int i = specify_x - constant; i <=specify_x + constant; i++){

      for (int j = specify_y - constant; j <= specify_y+ constant; j++)

      {

       if (i < 0 || j < 0 || i >= row || j >= col) {

        check = false;

        break;

       }

       if (matrix[i][j] != chr) {
        check = false;
        break;

       }

      }
     }
      if (check) {
       size += 2;
       constant++;
      }

     }

     System.out.println(size);
   

    }
  }

   sc.close();
 
  }

 }