中望笔试有无AC

第一题多源BFS,第二题不说了,第三题Leetcode原题

第一题多源BFS为什么通过率99.15%? 有无大佬AC

附上题目:给你一个mxn的矩阵,矩阵只包含以下元素: 0表示此处为山脉,1表示此处为农田,2表示此处为水源。水只能沿着上下左右四个方向流向相邻农田,山脉会阻挡水的流动。水从水源流向相邻农田需要花费1天时间,水从农田流向相邻农田也需要花费1天时间。你需要返回地图上所有农田都得到灌溉所花费的天数,否则返回-1。

示例:[[2,0],[1,1]],输出2

代码

class Solution {
public:
    int m,n,res;
    int dir[4][2] = { 0,1,0,-1,1,0,-1,0 };
    bool islegal(int x, int y)
    {
        if (x < 0 || x >= m || y < 0 || y >= n) return false;
        return true;
    }
    int irrigateFarmland(vector<vector<int> >& mtx)
    {
        m = mtx.size(), n = mtx[0].size();
        vector<vector<int>> vis(m, vector<int>(n, 0));
        queue <pair<int, int>> q;
        int farmArea = 0;
        int res = -1;
        int temp = 0;
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (mtx[i][j] == 2) {
                    q.emplace(i, j);
                    vis[i][j] = true;
                }
                else if (mtx[i][j] == 1) farmArea++;
            }
        }
        while (!q.empty())
        {
            res++;
            int m = q.size();
            for (int i = 0; i < m; i++)
            {
                auto x = q.front();
                q.pop();
                for (int k = 0; k < 4; k++)
                {
                    int nx = x.first + dir[k][0];
                    int ny = x.second + dir[k][1];
                    if (!islegal(nx, ny) || vis[nx][ny] || mtx[nx][ny] == 0) continue;
                    if (mtx[nx][ny] == 1)
                    {
                        vis[nx][ny] = 1;
                        q.emplace(nx, ny);
                        temp++;
                    }
                }
            }
        }
        return temp == farmArea ? res : -1;
    }
};

全部评论
猜一发,没农田应该返回0
2 回复 分享
发布于 2023-07-25 00:23 陕西
中望这么难?
1 回复 分享
发布于 2023-07-25 00:05 广东
请问中望笔试在投递多久之后会发呀?
点赞 回复 分享
发布于 2023-07-25 09:09 陕西
老哥投的是什么岗
点赞 回复 分享
发布于 2023-07-25 16:29 广东
大佬,试卷是B卷吗?考试时间1小时?
点赞 回复 分享
发布于 2023-07-28 18:35 四川
第三题我吐了,偏偏抽到了这个hard
点赞 回复 分享
发布于 2023-07-31 00:29 陕西
中望核心代码模式吗
点赞 回复 分享
发布于 2023-07-31 00:51 陕西
感觉有点像Leetcode腐烂的橘子
点赞 回复 分享
发布于 2023-08-03 09:59 辽宁

相关推荐

点赞 45 评论
分享
牛客网
牛客企业服务