[BOJ] 1025. 제곱수 찾기

import java.util.HashSet;
import java.util.Scanner;

public class Main {
	static HashSet<Integer> set = new HashSet<>();
	static int answer = -1;
	static int[][] map;
	static int N,M;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		map = new int [N][M];		
					
		for(int i = 0; i < map.length; i++) {
			String s = sc.next();
			for(int j = 0; j < s.length(); j++) {
				map[i][j] = s.charAt(j) - '0';
			}
		}
		
		for(int i = 0; i <= 33333; i++) {
			set.add(i*i);
		}
		
				
		selectDiff();
		System.out.println(answer);
		
	}
	
	public static void selectDiff() {
		for(int diff_y = -8; diff_y <= 8; diff_y++) {
			for(int diff_x = -8; diff_x <= 8; diff_x++) {
				selectStartPoint(diff_y, diff_x);
			}
		}
	}
	
	public static void selectStartPoint(int diff_y, int diff_x) {
		for(int st_y = 0; st_y < 9; st_y++) {
			for(int st_x = 0; st_x < 9; st_x++) {
				solve(diff_y,diff_x,st_y,st_x);
			}
		}
	}
	
	public static void solve(int diff_y, int diff_x, int st_y, int st_x) {
		StringBuilder sb = new StringBuilder();
		for(int num = 0; num < 9; num++) {
			if(isOutOfBound(st_y+diff_y*num,st_x+diff_x*num)) break;
			sb.append(map[st_y+diff_y*num][st_x+diff_x*num]);
			int val = Integer.parseInt(sb.toString());
			if(isSquaredNumber(val)) {
				answer = Math.max(answer, val);
			}
		}
		sb.delete(0,sb.length());
	}
	
	public static boolean isOutOfBound(int y, int x) {
		if(y < 0 || y >= N || x < 0 || x >= M) return true;
		return false;
	}
			
	public static boolean isSquaredNumber(int num) {
		if(set.contains(num)) return true;
		else return false;
	}					
}