UVa10908 - Largest Square－awesq123的部落格

1 // 1 test case

7 10 4 // row column number of pairs

abbbaaaaaa // map

abbbaaaaaa

aaaaaaaaaa

aaccaaaaaa

1 2 // row = 1, col = 2 (both row and column start from 0), output = 3 (square 'b')

2 4 // output = 1 (single 'a')

4 6

5 2 // output = 1

(0, 0)

b // output = 1

(1, 1)

bbb // output = 3

bbb

(1, 1)

abb // output = 1

bbb

-----

#include <stdio.h>

#define MAX 100

int main(int argc, char *argv[])
{
   char grids[MAX][MAX];
   int tes_cas; /* test cases */
   int rows, columns, pair_nums;
   int i;

   scanf("%d", &tes_cas);
   while(tes_cas--)
   {
       scanf("%d %d %d", &rows, &columns, &pair_nums); /* rows <= 100; colums <= 100; */
       printf("%d %d %d\n", rows, columns, pair_nums); /* request of problem */

       for(i = 0; i < rows; i++)
           scanf("%s", &grids[i]);

       while(pair_nums--)
       {
           int X, Y, lar_sqr = 1, start, ori_X, ori_Y, counter = 0; /* largest square */ /* original */
           int sqr_len; /* square length */

           scanf("%d %d", &ori_Y, &ori_X); /* Pay attention to the relative position of X and Y. */

           start = 1;
           sqr_len = 3;
           /* Search from the upper left corner of the square. */
           for(; ori_X-start >= 0 && ori_Y-start >= 0; start++, sqr_len += 2, counter = 0)
           {
               for(Y = ori_Y-start; Y < (ori_Y - start) + sqr_len && Y < rows; Y++)
                   for(X = ori_X-start; X < (ori_X - start) + sqr_len && X < columns; X++)
                       if(grids[Y][X] == grids[ori_Y][ori_X])
                           counter++;
                       else
                           break;
               if(counter == sqr_len*sqr_len)
                   lar_sqr += 2;
               else
                   break;
           }
           printf("%d\n", lar_sqr);
       }
   }
   return 0;
}

----

package uva10908;

import java.util.Scanner;

/**
*
* @author awesq
*/
public class UVa10908 {

/**
* @param args the command line arguments
*/
public static void main(String[] args) {
try (Scanner sc = new Scanner(System.in)) {
int cases = sc.nextInt();
while (cases-- > 0) {
int row, column, numberPairs;
row = sc.nextInt();
column = sc.nextInt();
numberPairs = sc.nextInt();
sc.nextLine(); // For the remaining carriage return or line feed.
System.out.println("" + row + " " + column + " " + numberPairs);

// Input
char[][] table = new char[row][column];
for (int i = 0; i < row; i++) {
String str = sc.nextLine();
for (int j = 0; j < str.length(); j++) {
table[i][j] = str.charAt(j);
}
}

// Number of pairs.
while (numberPairs-- > 0) {
int a = sc.nextInt();
int b = sc.nextInt();
System.out.println("" + findLargestSquare(a, b, row, column, table));
}

}
} catch (Exception e) {
}
}

public static int findLargestSquare(final int centralRow, final int centralCol, final int row, final int column, final char[][] table) {
int curLength = -1, offset = 0;
for (; centralRow - offset >= 0
&& centralRow + offset < row
&& centralCol - offset >= 0
&& centralCol + offset < column; curLength += 2, offset++) {
if (isSquare(centralRow - offset,
centralCol - offset,
centralRow + offset,
centralCol + offset,
table) == false) {
break;
}
}
return curLength;
}

public static boolean isSquare(final int startRow, final int startCol, final int endRow, final int endCol, final char[][] table) {
for (int i = startRow; i <= endRow; i++) {
for (int j = startCol; j <= endCol; j++) {
if (table[i][j] != table[startRow][startCol]) {
return false;
}
}
}
return true;
}
}