本系列记录翀翀😐痛苦的刷题日志，所有题目均来自于牛客网OJ题目，坚持刷题谈起来容易做起来难，希望我可以坚持下去，这里仍然分享一段励志文案：每个人都有梦想，然而有些人把梦想变成了现实，有些人的梦想依旧是梦想，只因为他们为梦想付出的努力程度不一样，他们坚持的时间不一样，最终才有这样的结果。

NC21669-牛牛与牛妹

题目链接

https://ac.nowcoder.com/acm/problem/21669

题目描述

给你一个网格，有些点被#覆盖了不能再走，其他点是空地，现在牛牛和牛妹轮流开始将空地变成#。 如果当前轮到的人操作之后左上角到右下角不存在通路了，当前操作的人就输了通路只能是从左上角到右下角往右或者往下走的路径牛牛先开始操作，如果双方都是绝顶聪明，输出最后谁赢保证一开始给你的网格是存在一条左上角到右下角的通路的，当然，左上角与右下角都是空地。

第一行输入两个整数n,m(2≤ n,m ≤ 20)，接下来n行每行输入m个字符用来描述网格。

测试样例

样例1

输入

2 2
..
..

输出

niuniu

样例2

输入

4 3
...
.#.
.#.
...

输出

niumei

样例3

输入

3 3
.##
..#
#..

输出

niumei

样例4

输入

4 4
....
...#
#...
....

输出

niuniu

解题思路

因为两个牛都很聪明，不会提前自杀式下棋。那么我们假设有一条通路，那么这个通路很显然长n+m，那么两个聪明的牛都不会提前在这个通路上下棋，除非他只能迫不得已下在这里，那么他就输家。又因为牛牛先下，所以如果剩下的.个数是奇数，那么最终一定是牛牛迫不得已下棋下在通路上，即输家。否则是牛妹。

解题代码

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    char s;
    int num = 0;
    for (int i = 0; i < n*m; i++)
    {
        cin >> s;
        if (s == '.')
        {
            num++;
        }
    }
    int cnt = num - n - m + 1;
    if (cnt % 2 == 1)
        cout << "niuniu" << endl;
    else
        cout << "niumei" << endl;
    system("pause");
    return 0;
}

NC21653-巨型迷宫

题目链接

https://ac.nowcoder.com/acm/problem/21653

题目描述

一个n行数字迷宫，每行都有无穷多个数，问你从起点走到终点经过的数字和的最小值，包括起点终点上面的数字。每一次可以走上下左右相邻的任意一个格子。这个数字迷宫比较特殊，每一列都是一模一样的。现在给你一个数组a,a[i] 表示第i行的数字是什么，再给你sx,sy, ex,sy分别表示起点与终点。

第一行输入一个整数n,sx,sy,ex,ey表示行数与起点终点

第二行输入n个数表示每一行的数字。1<=n<=50, 1<=a[i]<=10000<=sx,ex<=n-1, 0<=sy,ey<=109。

测试样例

样例1

输入

3 2 0 2 2
5 3 10

输出

29

样例2

输入

3 0 2 0 0
5 3 10

输出

15

样例3

输入

1 0 0 0 0
1

输出

1

解题思路

因为行数很少，所以直接暴力枚举就可以，主要就是模拟中有一点小细节即节点个数不要算多或算少即可。我们暴力枚举的思路是，每次必须经过第i行。最终遍历所有行以后选择和最小的即可。

解题代码

#include <bits/stdc++.h>
#define LL long long
#define INF 99999999999999

using namespace std;
const int N = 1e5 + 7;

int f(int a[], int i, int j)
{
    LL sum = 0;
    //必须是从最小行到最大行，所以比较起点和终点x
    int begin = min(i, j); //起点行数
    int end = max(i, j);   //终点行数
    while (begin <= end)
    {
        sum += a[begin]; //求解跨行的值之和
        begin++;
    }
    return sum;
}
int main()
{
    int a[N], sx, sy, ex, ey, n;
    cin >> n;
    cin >> sx >> sy >> ex >> ey;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    LL y = abs(ey - sy) + 1;    //跨的行数，细节：取绝对值后必须加1
    LL ans = INF;               //一开始初始化ans为最大值无穷
    for (int i = 0; i < n; i++) //遍历所有行，算的时候必须经过这个行
    {
        LL sum = y * a[i];   //横向相加
        sum += f(a, i, sx);  //以sx为起点，竖向相加
        sum -= a[i];         //去掉当前行的值，因为上面已经加过了
        sum += f(a, i, ex);  //ex为起点，竖向相加
        sum -= a[i];         //去掉当前行的值，因为上面已经加过了（最终以sx,ex为两端点，呈U型走向）
        ans = min(ans, sum); //更新最小值
    }
    cout << ans << endl;
    return 0;
}