백준 1577, 도로의 개수

개요

문제 링크
골드 5, DP
지나갈 수 없는 길을 고려한 2차원 경로 탐색

---

접근

1. K=50 으로 작으니까 길을 지나갈 수 없는지 찾을 때는 O(k)번 해주면 된다.
2. <pair,pair>를 vector에 저장하고 find 하면 되겠구나
   주의할 점 : 점의 대소관계를 고려하지 않고 입력이 들어오므로 비교해서 넣어주거나 넣은것에서 4가지를 찾아줘야 한다.
   4가지 = (왼쪽,현재), (현재,왼쪽), (아래,현재), (현재,아래)

---

Pseudo code

vector.push({x1,y1}, {x2,y2})
for (세로)
    for (가로)
        if (왼쪽과 현재를 잇는 선분이 vector에 있으면)
            왼쪽은 더하지 마라
        if (현재와 왼쪽을 잇는 선분이 vector에 있으면)
            왼쪽은 더하지 마라
        if (아래와 현재를 잇는 선분이 vector에 있으면)
            아래는 더하지 마라
        if (현재와 아래를 잇는 선분이 vector에 있으면)
            아래는 더하지 마라

---

Source code

#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> point;
typedef pair<point,point> line;
vector <line> q;

int Find(line l) {
    for (int i=0; i<q.size(); i++)
        if (q[i] == l)
            return 1;
    return 0;
}

int main() {
    int n, m, k;
    cin >> n >> m >> k;

    int x1, y1, x2, y2;
    for (int i=1; i<=k; i++) {
        cin >> x1 >> y1 >> x2 >> y2;
        q.push_back({{x1+1,y1+1},{x2+1,y2+1}});
    }

    long long dp[n+2][m+2];
    for (int i=0; i<=n+1; i++)
        for (int j=0; j<=m+1; j++)
            dp[i][j] = 0;

    dp[1][1] = 1;
    for (int i=1; i<=n+1; i++)
        for (int j=1; j<=m+1; j++) {
            if (i==1 && j==1)
                continue;
            line l1, l2;
            int c1 = 1, c2 = 1;

            l1 = {{i,j},{i-1,j}};
            l2 = {{i-1,j},{i,j}};
            if (Find(l1)) c1 = 0;
            if (Find(l2)) c1 = 0;

            l1 = {{i,j},{i,j-1}};
            l2 = {{i,j-1},{i,j}};
            if (Find(l1)) c2 = 0;
            if (Find(l2)) c2 = 0;

            dp[i][j] = c1*dp[i-1][j]+c2*dp[i][j-1];
        }
    cout << dp[n+1][m+1];
}