직사각형 마른 땅
면접 대비시간 제한7초메모리 제한1024 MB
0과 1로 이루어진 격자에서 1(습지)이 없는 가장 큰 직사각형의 넓이를 구합니다.
문제
플로리다에는 습지가 많아서 집을 지을 땅을 찾기 어렵다. 사람들이 집을 반드시 직사각형으로 짓겠다고 고집하면 이 문제는 더 심각해진다.
땅은 2차원 직사각형 격자이고, 각 칸은 젖은 땅이거나 마른 땅이다. 넓이가 가장 큰 직사각형 마른 땅을 찾아라. 즉 넓이가 가장 큰 집을 지을 수 있는 곳을 찾는 것이다. 집은 직사각형이어야 하므로, 사용하는 마른 칸들은 직사각형을 이루어야 하며 그 직사각형 안에 젖은 칸이 하나도 없어야 한다.
입력
첫 줄에 두 정수 ()과 ()가 주어진다. 각각 땅의 행 수와 열 수이다.
이어지는 개의 줄은 땅의 각 행을 나타낸다. 각 줄은 1번 열부터 시작하는 개의 문자로 이루어지며, 각 문자는 1(젖은 땅) 또는 0(마른 땅)이다.
출력
가장 넓은 직사각형 마른 땅의 넓이를 출력한다.