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

NC109-岛屿数量

题目链接

https://www.nowcoder.com/questionTerminal/0c9664d1554e466aa107d899418e814e

题目描述

给一个01矩阵，1代表是陆地，0代表海洋， 如果两个1相邻，那么这两个1属于同一个岛。我们只考虑上下左右为相邻。岛屿: 相邻陆地可以组成一个岛屿（相邻:上下左右） 判断岛屿个数。

测试样例

输入

[[1,1,0,0,0],[0,1,0,1,1],[0,0,0,1,1],[0,0,0,0,0],[0,0,1,1,1]]

输出

3

解题思路

dfs，从为1大陆块为起点，一直沿着1走，顺便把走过的标记为0，这样就可以防止再次重复走过这个大陆，每次走完一次知道不能在走了说明走完一个岛屿，增加岛屿数量。

解题代码

class Solution
{
public:
    /**
     * 判断岛屿数量
     * @param grid char字符型vector<vector<>> 
     * @return int整型
     */
    int m, n;
    //地图
    int Map[205][205];
    //四个方向向量
    int dir[4][2] = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
    void dfs(int x, int y)
    {
        //越界了就停止
        if (x < 0 || x >= m || y < 0 || y >= n || Map[x][y] == 0)
        {
            return;
        }
        //走过的大陆标记为0，防止再次走过
        if (Map[x][y] == 1)
            Map[x][y] = 0;
        //四个方向均再次尝试
        for (int i = 0; i < 4; i++)
        {
            dfs(x + dir[i][0], y + dir[i][1]);
        }
    }
    int solve(vector<vector<char>> &grid)
    {
        //m行n列
        m=grid.size();
        n = grid[0].size();
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                //因为给的是字符，所以要转换成整型
                Map[i][j] = grid[i][j]-'0';
            }
        }
//         for(int i=0;i<m;++i){
//             for(int j=0;j<n;++j)
//                cout<<Map[i][j];
//             cout<<endl;
// }
          //岛屿数量初始化为0
        int num=0;
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                //当时大陆时，可以作为起点
                if (Map[i][j] == 1)
                {
                    //必定走完一个道岛
                    dfs(i, j);
                    //增加岛的数量
                    num++;
                }
            }
        }
        return num;
    }
};

NC20035-打鼹鼠

题目链接

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

题目描述

鼹鼠是一种很喜欢挖洞的动物，但每过一定的时间，它还是喜欢把头探出到地面上来透透气的。根据这个特点阿Q编写了一个打鼹鼠的游戏：在一个n*n的网格中，在某些时刻鼹鼠会在某一个网格探出头来透透气。 你可以控制一个机器人来打鼹鼠，如果i时刻鼹鼠在某个网格中出现，而机器人也处于同一网格的话，那么这个鼹鼠就会被机器人打死。而机器人每一时刻只能够移动一格或停留在原地不动。 机器人的移动是指从当前所处的网格移向相邻的网格，即从坐标为（i,j）的网格移向(i-1, j),(i+1, j),(i,j-1),(i,j+1)四个网格，机器人不能走出整个n*n的网格。游戏开始时，你可以自由选定机器人的初始位置。 现在你知道在一段时间内，鼹鼠出现的时间和地点，希望你编写一个程序使机器人在这一段时间内打死尽可能多的鼹鼠。

第一行为n（n ≤ 1000）, m（m ≤ 10000），其中m表示在这一段时间内出现的鼹鼠的个数，
接下来的m行每行有三个数据time,x,y表示有一只鼹鼠在游戏开始后time个时刻，在第x行第y个网格里出现了一只鼹鼠。
Time按递增的顺序给出。注意同一时刻可能出现多只鼹鼠，但同一时刻同一地点只可能出现一只鼹鼠。

测试样例

输入

2 2
1 1 1
2 2 2

输出

1

解题思路

这道题一开始想使用bfs来做，但是超时严重，并且难以存储，后来查看题解后才知道是使用dp来做，因为时间给的是默认递增排序。我们声明dp[i]表示为在抓到第i只小鼠时最多之前能抓到多少只小鼠。所以
dp[j]是上一只抓到的小鼠。所以一开始就将所有的dp[i]初始化为1即都原地守株待兔必定可以抓到一只。又因为此题涉及到了能否到达的问题，所以需要满足曼哈顿距离小于等于时间差才可以。

解题代码

#include <bits/stdc++.h>
using namespace std;
int dp[10005], n, m, _time[10005], _x[10005], _y[10005], ans; //dp[i]表示到第i只时能打多少只
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        cin >> _time[i] >> _x[i] >> _y[i];
    }
    for (int i = 1; i <= m; i++)
    {
        dp[i] = 1;
    }
    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j < i; j++)
        {
            //如果曼哈顿距离小于时间差
            if (abs(_x[i] - _x[j]) + abs(_y[i] - _y[j]) <= abs(_time[i] - _time[j]))
            {
                //那么可以抓到这只小鼠，比较dp[i]和通过dp[j]+1得到的哪个方法更好
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }
    for (int i = 1; i <= m; i++)
    {
        ans = max(ans, dp[i]);
    }
    cout << ans << endl;
    system("pause");
    return 0;
}