프로그래머스 : 등굣길

문제링크 :https://programmers.co.kr/learn/courses/30/lessons/42898

프로그래머스

 

 문제 설명 

 

(1,1) 좌표에서 출발 -> (m,n)좌표까지가능 경로의수 %1000000007 을 return 중간에 우물이 있으니 우물은                피해서 가야됨.

 

 알고리즘 

 

1. map[i][1] , map[1][i]를 1로 초기화 하고 . 우물은 -1로  초기화 해준다.

2. map[i][j]= map[i-1][j]+map[i][j-1] 점화식을 이용하여  map[m][n]을 구하면 된다.

 

 코드 

#include <string>
#include <vector>
using namespace std;
 
int map[110][110];
 
int solution(int m, int n, vector<vector<int>> puddles) {
 
    for (int i = 1; i <= m; i++) map[i][1] = 1;
  
    for (int j = 1; j <= n; j++) map[1][j] = 1;
 
 
    for (int i = 0; i < puddles.size(); i++) {
        map[puddles[i][0]][puddles[i][1]] = -1;
    }
 
 
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            //시작점
            if (i == 1 && j == 1)continue;
 
            //우물
            if (map[i][j] == -1) map[i][j] = 0;
 
            //정상적인 경로
            else map[i][j] = (map[i - 1][j] + map[i][j - 1]) % 1000000007;
 
        }
    }
 
}