中望笔试有无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; } };