题目链接：https://ac.nowcoder.com/acm/problem/213383

到主站看：https://blog.csdn.net/weixin_43346722/article/details/109559063

题目

有一块大小为 行 列的板子，每个位置可能是一个小球，用 'o' 表示，可能是障碍物，用 'x' 表示，也可能空无一物，用 '.' 来表示。

每个小球可以向左向右或者向下移动，但是不能向上移动，或者和某个小球重叠，也不能越出板子。

每个小球向下移动一个单位，牛牛可以获得一分。

牛牛想知道对于某个开始状态，能得到的最大分数是多少。

输入

第一行输入一个整数 ，表示板子的行数。

随后 行，每行一个长度为 的字符串，如题意所示。

设有 个小球。

对于 的数据有 。

另有 的数据 。

对于 的数据有 。

对于 的数据有 。

输出

一行一个整数表示答案。

样例输入

10
oo
.o
.x
x.
..
oo
.o
x.
..
x.

样例输出

12

样例解释

最终结果为：

..
oo
ox
x.
..
..
..
x.
oo
xo

思路

这道题是一道贪心。

就直接从下向上枚举，然后就每次把每一个小球放在尽可能下面的地方。
至于能放到哪里就拿一个队列记录可以放的位置，那么每次拿到的位置就是最下面的（因为你是从下往上枚举的）
然后如果区间断开，就把队列清空。

至于判断区间是否断开，就是三种情况：

1. 某一行两个都是墙
2. 行左边的是墙， 行右边的是墙
3. 行右边的是墙， 行左边的是墙

比赛时

想到贪心做法，结果忘了可以用队列记录位置，然后只能打了个 dfs，拿了个 分。

代码

#include<cstdio>
#include<iostream>

using namespace std;

int n, ans, have[300001][3], pla[300001], high;
char c[300001][3];

int main() {
    scanf("%d", &n);

    for (int i = 1; i <= n; i++) {
        c[i][1] = getchar();
        while (c[i][1] != 'o' && c[i][1] != '.' && c[i][1] != 'x') c[i][1] = getchar();
        c[i][2] = getchar();
        while (c[i][2] != 'o' && c[i][2] != '.' && c[i][2] != 'x') c[i][2] = getchar();
    }

    pla[0] = 0;
    high = 1;
    for (int i = n; i >= 1; i--) {
        for (int j = 1; j <= 2; j++) {
            if (c[i][j] == 'o') {
                if(pla[high] > i && pla[0] >= high) {//球能向下走
                    ans += pla[high] - i;
                    high++;
                    pla[++pla[0]] = i;
                }
            }
            else if (c[i][j] == '.') pla[++pla[0]] = i;//有能放的位置
        }
        if ((c[i][1] == 'x' && c[i][2] == 'x') || (c[i][1] == 'x' && c[i - 1][2] == 'x') || (c[i - 1][1] == 'x' && c[i][2] == 'x')) {
            pla[0] = 0;
            high = 1;
        }//被分割到新的区域
    }

    printf("%d", ans);

    return 0;
}