1577번: 도로의 개수

https://www.acmicpc.net/problem/1577


$O(nm+k)$

#include<cstdio>
#define min(x,y) x<y?x:y
int n, m, k, a[101][101][2], x1, y1, x2, y2;
long long dp[102][102] = { 1 };
int main() {
    scanf("%d%d%d", &n, &m, &k);
    while (k--) {
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        x1^x2 ? a[min(x1, x2)][y1][0] = 1 : a[x1][min(y1, y2)][1] = 1;
    }
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= m; j++) dp[i + 1][j] += (1 - a[i][j][0])*dp[i][j], dp[i][j + 1] += (1 - a[i][j][1])*dp[i][j];
    printf("%lld", dp[n][m]);
    return 0;
}