[BOJ-1577]도로의개수

http://acmicpc.net/problem/1577

[풀이방법]

DP

도로의 크기 map[row][col]

도로 dp[r][c] , 에 경우의 수로 들어올 수 있는 것은 [r-1][c] / [r][c-1] 에서 올 수 있는 길이 존재한다. (위, 왼쪽에서 이동이 가능하다.)

위 방법은 모든 경우 이동이 가능한 경우에 구할 수 있다. 

하지만 이동할 수 없는 경우가 주어지기 때문에 각 위치에 이동할 수 없는 부분을 추가한다.

 vector<pos> unable을 추가해서 도로가 없는 것을 벡터값에 추가해준다.

그리고 unable에서 있는 좌표인 경우 값을 가져오지 않는 방법으로 풀이 할 수 있다. 

[C++ source code]

#include<cstdio>
#include<vector>
#define din2(a,b) scanf("%d%d", &a, &b)
using namespace std;
const int dr[] = {-1,0}; // 
const int dc[] = {0,-1}; //
const int m = 111;
typedef long long ll;
int row, col;
 
struct pos {
    int r, c;
    pos() {}
    pos(int ir, int ic) : r(ir), c(ic) {}
};
 
struct info {
    ll number;
    vector<pos> unable;
    info() {
        number = 0;
    }
};
info im[m][m]; // 
 
int main() {
    din2(row, col);
    int cond;
    scanf("%d", &cond);
    for (int i = 0; i < cond; i++) {
        int a, b, c, d;
        din2(a, b);
        din2(c, d);
        // TODO
        im[a][b].unable.push_back(pos(c, d));
        im[c][d].unable.push_back(pos(a, b));
    }
    im[0][0].number = 1;
    for (int r = 0; r <= row; r++) {
        for (int c = 0; c <= col; c++) {
            if (r == 0 && c == 0) continue;
            for (int di = 0; di < 2; di++) {
                int tr = r + dr[di];
                int tc = c + dc[di];
                bool is_unable = false;
                if (tr < 0 || row < tr || tc < 0 || col < tc) continue;
                for (auto unablepos : im[r][c].unable) {
                    if (tr == unablepos.r && tc == unablepos.c) is_unable = true;
                }
                if (is_unable) continue;
                im[r][c].number += im[tr][tc].number;
            }
        }
    }
    printf("%lld", im[row][col].number);
 
    return 0;
}