【題解】e581: 11067 – Little Red Riding Hood

【題目敘述】https://zerojudge.tw/ShowProblem?problemid=e581
【解題想法】DP 找路徑組合數

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
#define pii pair<int,int>
#define F first
#define S second
const int maxn = 105;
int g[maxn][maxn];

int main() {
    int w, h, n, x, y;
    while (cin >> w >> h && w+h){
        memset(g, 0, sizeof(g));
        cin >> n;
        while (n--){
            cin >> x >> y;
            g[x][y] = -1;
        }
        g[0][0] = 1;
        for (int i = 0; i <= w; i++){
            for (int j = 0; j <= h; j++){
                if (g[i][j] == -1) continue;
                if (i && g[i-1][j] != -1){
                    g[i][j] += g[i-1][j];
                }
                if (j && g[i][j-1] != -1){
                    g[i][j] += g[i][j-1];
                }
            }
        }
        
        if (g[w][h] <= 0) cout << "There is no path.\n";
        else if (g[w][h] == 1) cout << "There is one path from Little Red Riding Hood's house to her grandmother's house.\n";
        else cout << "There are " << g[w][h] << " paths from Little Red Riding Hood's house to her grandmother's house.\n";
    }
    return 0;
}
分享本文 Share with friends