西南交通大学算法分析与设计实验5.3

 

 

 

---

本文仅给出实现的代码，代码仅经过简单的样例测试，不保证逻辑完全正确。

#include "iostream"

using namespace std;

int n, m, result;
// 标记该位置是否为大厦
int house[1001][1001];
// dp数组
int dp[1001][1001];

// 两个点是否被大厦阻挡
int Check(int x, int y, int x1, int y1) {
    bool left_up_1 = house[x - 1][y - 1];
    bool left_down_1 = house[x][y - 1];
    bool right_up_1 = house[x - 1][y];
    bool right_down_1 = house[x][y];
    bool left_up_2 = house[x1 - 1][y1 - 1];
    bool left_down_2 = house[x1][y1 - 1];
    bool right_up_2 = house[x1 - 1][y1];
    bool right_down_2 = house[x1][y1];
    if (x == 0) {
        left_up_1 = false;
        right_up_1 = false;
    }
    if (y == m) {
        right_up_1 = false;
        right_down_1 = false;
    }
    if (x1 == 0) {
        left_up_2 = false;
        right_up_2 = false;
    }
    if (y1 == m) {
        right_up_2 = false;
        right_down_2 = false;
    }
    // 两个点有一个在大厦内部
    if ((left_up_1 && left_down_1 && right_up_1 && right_down_1) || (left_up_2 && left_down_2 && right_up_2 && right_down_2)) {
        return 1;
    }
    // 左右阻挡
    if ((left_up_1 && left_down_1 && right_up_2 && right_down_2) || (left_up_2 && left_down_2 && right_up_1 && right_down_1)) {
        return 1;
    // 上下阻挡
    } else if ((right_up_1 && left_up_1 && right_down_2 && left_down_2) || (right_up_2 && left_up_2 && right_down_1 && left_down_1)) {
        cout << "x: " << x << " y: " << y << " x1: " << x1 << " y1: " << y1 << endl;
        return 1;
    }
    return 0;
}

void Solve() {
    // 初始化左下角
    dp[n][0] = 0;
    // 初始化最下面的行
    for (int i = n + 1; i >= 0; i--) {
        dp[n][i] = 1;
    }
    // 初始化最左边的列
    for (int i = 0; i <= m; i++) {
        dp[i][0] = 1;
    }
    // 从左下角开始遍历
    for (int i = n - 1; i >= 0; i--) {
        for (int j = 1; j <= m; j++) {
            if (Check(i, j, i, j)) {
                dp[i][j] = -1;
                continue;
            }
            if (!Check(i, j, i + 1, j) && !Check(i, j, i, j - 1)) {
                dp[i][j] = dp[i + 1][j] + dp[i][j - 1];
                continue;
            }
            if (Check(i, j, i + 1, j)) {
                dp[i][j] = dp[i][j - 1];
                continue;
            }
            if (Check(i, j, i, j - 1)) {
                dp[i][j] = dp[i + 1][j];
                continue;
            }
            if (Check(i, j, i - 1, j)) {
                dp[i][j] = dp[i][j + 1];
                continue;
            }
            if (Check(i, j, i, j + 1)) {
                dp[i][j] = dp[i - 1][j];
                continue;
            }
        }
    }
    result = dp[0][m];
}

int main() {
    cin >> n >> m;
    int num;
    cin >> num;
    for (int i = 0; i < num; i++) {
        int x, y, height, width;
        cin >> x >> y >> height >> width;
        // 标记大厦
        for (int j = x - 1; j < x + height - 1; j++) {
            for (int k = y - 1; k < y + width - 1; k++) {
                house[j][k] = true;
            }
        }
    }
    Solve();
    cout << "There is totally " << result << " ways to get out." << endl;
    for (int i = 0; i < n;i ++) {
        for (int j = 0; j < m; j++) {
            cout << house[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
    for (int i = 0; i <= n; i ++) {
        for (int j = 0; j <= m; j++) {
            ::printf("%4d", dp[i][j]);
        }
        cout << endl;
    }
    return 0;
}
/*
//样例1
5 6
1
2 4 3 2
//样例2
2 2 1 1 2 2 1

 */

样例1输出：

 

样例2输出：

 

---

如若发现问题，欢迎指正。