문제출저 :
https://www.acmicpc.net/problem/1915
1915번: 가장 큰 정사각형
첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다.
www.acmicpc.net
소스코드 :
import java.util.*;
import java.lang.*;
import java.io.*;
public class Main {
static int n,m;
static int[][] board;
static int[][] dp;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
board = new int[n+1][m+1];
dp = new int[n+1][m+1];
for(int i = 1; i <= n; i++)
{
String one = br.readLine();
for(int j = 1; j <= m; j++)
{
dp[i][j] = board[i][j] = (int)(one.charAt(j-1) - '0');
}
}
int answer = 0;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
if(board[i][j] == 1)
{
dp[i][j] = check(i, j);
answer = Math.max(answer, dp[i][j]);
}
}
}
System.out.println(answer * answer);
br.close();
}
public static int check(int y, int x)
{
int one = dp[y-1][x-1];
int two = dp[y][x-1];
int thr = dp[y-1][x];
if(one == 0 || two == 0 || thr == 0) return 1;
return Math.min(one, Math.min(two, thr)) + 1;
}
}