쓰레기 치우기
시간 제한2초메모리 제한128 MB
격자에서 왼쪽 위부터 오른쪽 아래까지 우측 또는 아래로만 이동하는 경로들로 모든 쓰레기 칸을 덮는 데 필요한 최소 로봇 수를 구하는 문제입니다.
문제
방은 세로 N, 가로 M인 격자판으로 나타낸다. 왼쪽 위 칸의 좌표를 (0, 0), 오른쪽 아래 칸의 좌표를 (N - 1, M - 1)이라고 하자. 몇몇 칸에는 쓰레기가 놓여 있다.
로봇 한 대는 왼쪽 위 칸에서 출발해 오른쪽 아래 칸에 도착해야 한다. 이동할 때는 현재 칸에서 오른쪽 또는 아래쪽으로만 갈 수 있으며, 지나가는 칸의 쓰레기를 수거할 수 있다.
모든 쓰레기를 수거하려면 최소 몇 대의 로봇이 필요한지 구하라.
입력
첫째 줄에 N과 M이 공백으로 구분되어 주어진다. (1 ≤ N, M ≤ 100)
다음 N개의 줄에는 각 줄마다 M개의 수가 주어진다. 값이 0이면 해당 칸이 비어 있고, 1이면 해당 칸에 쓰레기가 있다는 뜻이다.
출력
모든 쓰레기를 수거하는 데 필요한 로봇의 최소 대수를 출력한다.