GT혹성에 개미들은 특이하게 땅을 정사각형형태로 파고 판 곳에 사다리를 설치한다.
개미들이 판 곳에 사다리가 설치가 가능하면 1로 표시를 해 두고 사다리를 설치할 수 없는 지역은 0으로 표시되어 있다.
이때 1로 연결된(가로,세로) 지역에 사다리를 건설이 가능하다.
가장 큰 사다리의 크기와 설치해야 하는 사다리의 개수를 출력하자.
사다리의 크기는 1로 연결된 개수를 이야기하는 것이고
연결된 사다리는 하나로 본다.
GT혹성에 개미들은 특이하게 땅을 정사각형형태로 파고 판 곳에 사다리를 설치한다.
개미들이 판 곳에 사다리가 설치가 가능하면 1로 표시를 해 두고 사다리를 설치할 수 없는 지역은 0으로 표시되어 있다.
이때 1로 연결된(가로,세로) 지역에 사다리를 건설이 가능하다.
가장 큰 사다리의 크기와 설치해야 하는 사다리의 개수를 출력하자.
사다리의 크기는 1로 연결된 개수를 이야기하는 것이고
연결된 사다리는 하나로 본다.
입력으로 개미가 판 땅굴의 한변의 길이가 n이 입력된다.(1<=n<=100)
다음 줄 부터 n번째 줄까지 공백으로 구분하여 개미들이 표시한 값이 입력된다.
가장 큰 사다리의 크기와 설치한 사다리 개수를 설치하자
5
1 1 1 1 0
0 1 1 1 0
0 0 0 0 0
1 1 0 0 0
1 0 0 1 07 3가로세로 연결된 형태에서 가장 큰 것은 7개이고 사다리는 총 3개이다.
backtracking을 이용하시면 쉽게 풀립니다.