90分求助,查了很久没找到哪里问题。

novice 刷题 2022-03-27 16:30:02 2022-03-27 19:43:22 14
#include <bits/stdc++.h>
struct path {
    int x, y;
};
using namespace std;

int v[4][2] = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };
path s[260000];   //路径记录
int f[505][505];  //是否去过0表示没去过,1表示去过,广搜原则,去过的将不再去;
int t[600];       //最后一层能否到达;
path b[600];
int a[505][505];

bool cmp(path a, path b) {
    if (a.y == b.y)
        return (a.x < b.x);
    return (a.y > b.y);
}
int main() {
    path mid;

    int i, j, n, m, k, g, cc = 0, l, r;

    freopen("flow.in", "r", stdin);
    freopen("flow.out", "w", stdout);
    cin >> n >> m;

    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++) scanf("%d", &a[i][j]);

    memset(t, 0, sizeof(0));
    a[1][0] = -10086;
    a[1][m + 1] = -10086;

    for (i = 1; i <= m; i++) {
        if (a[1][i] < a[1][i - 1] || a[1][i] < a[1][i + 1])//第一层左右可以互相流动时,则不需要重复搜
            continue;
        else {
            cc++;
            memset(f, 0, sizeof(f));

            //设定边界
            for (j = 0; j <= n + 1; j++) {
                f[j][0] = 1;
                f[j][m + 1] = 1;
            }

            for (j = 0; j <= m + 1; j++) {
                f[0][j] = 1;
                f[n + 1][j] = 1;
            }
            b[cc].x = m + 1;
            b[cc].y = 0;
            //BFS
            k = 0;
            g = 0;
            s[0].x = 1;
            s[0].y = i;
            while (k <= g) {
                f[s[k].x][s[k].y] = 1;  //标记s[k]位置去过了;
                if (s[k].x == n)        //到底部了
                {
                    b[cc].x = min(b[cc].x, s[k].y);//如果最后可以联通,则底部是具备连续性的
                    b[cc].y = max(b[cc].y, s[k].y);//
                    t[s[k].y] = 1;//统计能到底部的有多少个
                }
                for (j = 0; j < 4; j++) {
                    mid.x = s[k].x + v[j][0];
                    mid.y = s[k].y + v[j][1];  //中转区域

                    if (!f[mid.x][mid.y] && a[mid.x][mid.y] < a[s[k].x][s[k].y])  //没去过,并且可以去;
                    {
                        g++;
                        s[g].x = mid.x;
                        s[g].y = mid.y;
                    }
                }
                k++;
            }
            if (b[cc].x == m + 1)
                cc--;
        }
    }

    int sum = 0;

    //统计底层是否能全部到达
    for (i = 1; i <= m; i++)  sum += t[i];

    if (sum < m)
        cout << "0"
             << "\n"
             << m - sum;
    else
    //线段覆盖
    {
        sort(b + 1, b + 1 + cc, cmp);
        int vv = 0, tt = m, st = 1;
        while (tt > 0) {
            l = b[st].x;
            r = st;
            for (i = st + 1; i <= cc; i++)
                if (b[i].y >= tt) {
                    if (b[i].x < l) {
                        l = b[i].x;
                        r = i;
                    }
                }
          else break;
            vv++;
            tt = l - 1;
            st = i;
        }

        cout << "1"
             << "\n"
             << vv << endl;
    }

    fclose(stdin);
    fclose(stdout);
    return 0;
}
{{ vote && vote.total.up }}

共 2 条回复

bc03 黄金三

建议附加scanf printf @novice

bc03 黄金三

@novice 建议用函数