1025번: 정사각형 찾기

https://www.acmicpc.net/problem/1025


$O(nm(n+m))$

가능한 모든 경우를 조사

#include<cstdio>
#include<cmath>
int n, m, a[9][9], r = -1;
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) scanf("%1d", &a[i][j]);
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            for (int k = -n; k < n; k++) {
                for (int l = -m; l < m; l++) {
                    int s = 0, x = i, y = j;
                    do {
                        s = s * 10 + a[x][y];
                        if (sqrt(s)*(int)sqrt(s) == s && r < s) r = s;
                        x += k;
                        y += l;
                    } while (x >= 0 & y >= 0 && x < n&&y < m && (k | l));
                }
            }
        }
    }
    printf("%d", r);
    return 0;
}