Coloring A Border [LeetCode 1034]

https://leetcode.com/contest/weekly-contest-134/problems/coloring-a-border/

2次元グリッドがある。
各要素には数が書いてある。
同じ数で隣接している要素は連結成分になる。
ある要素(r0,c0)に色colorを使って数を変更する。
(r0,c0)と連結な成分の要素の中でborderなものをcolorに変更する。
borderとは、4方向のいずれかが壁か、異なる連結成分であることを指す。

1≦縦横≦50
1≦色≦1000

前提知識

• UnionFind

解説

https://leetcode.com/submissions/detail/225427506/

連結成分であるかどうかはUnionFindに任せることにしよう。
連結成分判定ができたら、あとは、borderであるかを判定して、書き込んで返す。

class Solution {
public:
	vector<vector<int>> colorBorder(vector<vector<int>>& grid, int r0, int c0, int color) {
		int H = grid.size();
		int W = grid[0].size();

		UnionFind uf(H * W);
		rep(y, 0, H) rep(x, 0, W) rep(d, 0, 4) {
			int xx = x + dx[d];
			int yy = y + dy[d];
			if (xx < 0 or W <= xx or yy < 0 or H <= yy) continue;
			if (grid[yy][xx] != grid[y][x]) continue;

			int a = y * W + x;
			int b = yy * W + xx;
			uf(a, b);
		}

		rep(y, 0, H) rep(x, 0, W) {
			int a = y * W + x;
			int b = r0 * W + c0;
			if (uf[a] != uf[b]) continue;
			
			int ok = 0;
			rep(d, 0, 4) {
				int xx = x + dx[d];
				int yy = y + dy[d];
				if (xx < 0 or W <= xx or yy < 0 or H <= yy) {
					ok = 1;
					continue;
				}
				int c = yy * W + xx;

				if (uf[a] != uf[c]) {
					ok = 1;
					continue;
				}
			}
			
			if(ok) grid[y][x] = color;
		}

		return grid;
	}
};