앳코더90 - 012 - Red Painting（★4）

https://atcoder.jp/contests/typical90/tasks/typical90_l?lang=ja

012 - Red Painting（★4）

 

플젝들이 다 끝났으니 다시 초심을 되찾아 실력을 쌓으러 돌아왔다. 실력을 쌓기에 11번은 별 개수가 조금 많기에 상대적으로 더 쉬운 12번부터 풀어보았다.

 

해석을 보면 H, W 크기의 2차원 배열이 있고 두 종류의 쿼리가 주어진다.

- a, b 위치를 색칠한다.

- a,b,c,d  a,b가 색칠되어있고 c,d가 색칠되어 있을때 a,b -> c,d로 색칠된 면을 따라서만 상하좌우로 움직여서 도달할 수 있으면 yes 아니면 no

 

간단한 구현만 생각하면 색칠해놓고 색칠하는순간 bfs를 돌려서 가능한지 처리해주면 된다. 하지만 쿼리마다 bfs를 돌리면 시간초과 나는건 당연치사. 그렇다면 쿼리를 물어보는 순간 연결 가능한지 알 수 있는 방법이 있지않을까?

 

비슷한 문제를 본적이 있다.

https://www.acmicpc.net/problem/3197

3197번: 백조의 호수

 

백조의 호수라는 문젠데 해당 문제에서 사용하는 테크닉을 위에서 적용할 수 있다. union-find를 이용하여 색칠할때마다 merge해주면 쿼리가 들어왔을때 같은 집합인지 확인하면 된다. 이차원 배열을 일차원 배열에 저장하기 위해 y*2000 + x 형태로 저장하였다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <unordered_set>
#include <numeric>
#include <random>
#include <iostream>

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define range(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef vector<int> vi;
typedef vector<long long> vll;

const int INF = 200000000;
const double pi = 3.14159265358979;
const ll MOD = 987654321;

void yesno(bool a)
{
	if(a)
		cout << "Yes\n";
	else
		cout << "No\n";
}

int par[4005002];
int H, W;
int Q;
int arr[2002][2002]; 
int a, b, c, d, e;
int dy[4] = { 1,0,-1,0 };
int dx[4] = { 0,1,0,-1 };

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

void merge(int x, int y)
{
	x = find(x);
	y = find(y);

	if (x < y)
		par[y] = x;
	else
		par[x] = y;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	for (int i = 1; i <= 2000 * 2000 + 1; i++)
		par[i] = i;

	cin >> H >> W;

	cin >> Q;

	while (Q--)
	{
		cin >> a;
		if (a == 1)
		{
			cin >> b >> c;
			arr[b][c] = 1;
			for (int i = 0; i < 4; i++)
			{
				int ny = b + dy[i];
				int nx = c + dx[i];

				if (ny <= 0 || nx <= 0 || ny > H || nx > W)
					continue;
				if (!arr[ny][nx])
					continue;

				merge(b * 2000 + c, ny * 2000 + nx);
			}
		}
		else
		{
			cin >> b >> c >> d >> e;
			yesno(arr[b][c] && arr[d][e] && find(b * 2000 + c) == find(d * 2000 + e));
		}
	}
	
	return 0;
}