Eagle233-Blog

[Algorithm] 算法训练 202604

2026-04-14 15:21:50   2026-04-14 15:21:50
Categories Algorithm
Tags

1.3k Words   |   6 Minutes 

int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1};

void bfs(vector<vector<char>>& grid, int i, int j, vector<vector<bool>>& visited) {
	queue<pair<int, int>> q;
	q.push({i, j});
	visited[i][j] = true;
	while (!q.empty()) {
		pair<int , int> p = q.front(); q.pop();
		auto curi = p.first, curj = p.second;
		for (int k = 0; k < 4; k++) {
			auto nexti = curi + dir[k][0], nextj = curj + dir[k][1];
			if (nexti < 0 || nextj < 0 || nexti >= grid.size() || nextj >= grid[0].size() || grid[nexti][nextj] == '0' || visited[nexti][nextj]) continue;
			visited[nexti][nextj] = true;
			q.push({nexti, nextj});
		}
	}
}

void dfs(vector<vector<char>>& grid, int i, int j, vector<vector<bool>> &visited) {
	visited[i][j] = true;
	for (int k = 0; k < 4; k++) {
		auto nexti = i + dir[k][0], nextj = j + dir[k][1];
		if (nexti < 0 || nexti >= grid.size() || nextj < 0 || nextj >= grid[0].size() || visited[nexti][nextj] || grid[nexti][nextj] != '1') {
			continue;
		}
		dfs(grid, nexti, nextj, visited);
	}
}
static const int n = 205;
int father[n];
void init() {
	for (int i = 0; i < n; i++) {
		father[i] = i;
	}
}

int find(int x) {
	if (father[x] == x) {
		return x;
	}
	father[x] = find(father[x]);
	return father[x];
}

void join(int x, int y) {
	x = find(x);
	y = find(y);
	if (x == y) {
		return;
	}
	father[x] = y;
}

bool isSame(int x, int y) {
	return find(x) == find(y);
}
Page views: Loading...  ·  Visitors: Loading...
Except where otherwise noted, original content on this site is dedicated to the public domain under CC0 1.0.
Powered by Hexo & Theme mdsuper
沪ICP备2026040813号
Search