2/7 등굣길

[skarltjr]

package algo;

// m = col
// n = row
// 오른쪽과 아래쪽으로만 움직여 이동할ㅇ 수 있다
// 어차피 오른쪽과 아래쪽으로만 움직여서 이동할 수 있는 모든 경로는 최단경로다
// 1,1 부터 m,n까지 경로수 합 구하는 공식만 쓰면 알아서 최단경로다. 웅덩이만 피하고
// 그럼 2차배열의 판을 만들고  각 경로의 수를 저장하고 최종적으로 m,n의 값을 리턴
// 웅덩이가 있는 곳은 아예 못가게 해야한다

public class Solution {
    public int solution(int m, int n, int[][] puddles) {
        int[][] board = new int[n+1][m+1];
        for (int i = 0; i < puddles.length; i++)
        {
            int c = puddles[i][0];
            int r = puddles[i][1];
            board[r][c] = -1;
        }

        board[1][1] = 1;
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {

                if (i == 1 && j == 1)
                {
                    continue;
                }
                if (board[i][j] == -1)
                {
                    continue;
                }
                if (i > 1 && board[i-1][j] != -1)
                {
                    board[i][j] += board[i - 1][j]%1000000007;
                }
                if (j > 1 && board[i][j-1] != -1)
                {
                    board[i][j] += board[i][j - 1]%1000000007;
                }
            }
        }
        return board[n][m]%1000000007;
    }
}