Hatena::Grouptopcoder

tsubosakaの日記

2009-02-08

SRM 434 Div1 Easy

| 04:03

初項の場所と列行の公差を全探索するだけ。ただし、数列は最長のものだけではなくて部分列もチェックする必要がある。そこを忘れていた人がかなりいた。あとSystem Testで落ちていた人で多分sqrtの誤差で落ちているような人がいた。

public class FindingSquareInTable {
  public int findMaximalSquare(String[] table) {
    int H = table.length;
    int W = table[0].length();
    int t[][] = new int[H][W];
    for(int i = 0 ; i < H ; i++)
      for(int j = 0 ; j < W ; j++)
        t[i][j] = table[i].charAt(j) - '0';
    int square[] = new int[32000];
    for(int i = 0 ; i < square.length ; i++){
      square[i] = i * i;
    }
    int max = -1;
    for(int sx = 0 ; sx < W ; sx++){
      for(int sy = 0 ; sy < H ; sy++){
        for(int dx = -9 ; dx <= 9 ; dx++){
          for(int dy = -9 ; dy <= 9 ; dy++){
            if(dx == 0 && dy == 0)continue;
            int x = sx;
            int y = sy;
            int v = t[y][x];
            while(true){
              x = x + dx;
              y = y + dy;
              if(x < 0 || y < 0 || x >= W || y >= H)break;
              v = v * 10 + t[y][x];
              if(max < v && Arrays.binarySearch(square, v) >= 0){
                max = v;
              }
            }
            if(max < v && Arrays.binarySearch(square, v) >= 0){
              max = v;
            }
          }
        }
      }
    }
    return max;
  }
}