LeetCode 934. 最短的桥
原题链接
中等
作者:
我是java同学
,
2023-12-30 15:43:53
,
所有人可见
,
阅读 31
#define x first
#define y second
typedef pair<int, int> PII;
class Solution {
public:
int n, m;
vector<vector<int>> g, dist;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
queue<PII> q;
void dfs(int x, int y) {
g[x][y] = 0;
q.push({x, y});
dist[x][y] = 0;
for (int i = 0; i < 4; i ++ ) {
int a = x + dx[i], b = y + dy[i];
if (a >= 0 && a < n && b >= 0 && b < m && g[a][b])
dfs(a, b);
}
}
int bfs() {
while (q.size()) {
auto t = q.front();
q.pop();
for (int i = 0; i < 4; i ++ ) {
int a = t.x + dx[i], b = t.y + dy[i];
if (a >= 0 && a < n && b >= 0 && b < m && dist[a][b] > dist[t.x][t.y] + 1) {
dist[a][b] = dist[t.x][t.y] + 1;
if (g[a][b]) return dist[a][b] - 1;
q.push({a, b});
}
}
}
return -1;
}
int shortestBridge(vector<vector<int>>& grid) {
g = grid;
n = grid.size(), m = grid[0].size();
dist = vector<vector<int>> (n, vector<int>(m, 1e9));
for (int i = 0; i < n; i ++ )
for (int j = 0; j < m; j ++) {
if (g[i][j]) {
dfs(i, j);
return bfs();
}
}
return -1;
}
};