제출 #651114

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
651114		ymm	Furniture (JOI20_furniture)	C++17	100 / 100	376 ms	15132 KiB

furniture

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 1024;
bool has_a[N][N], has_b[N][N], has_furn[N][N];
int n, m;

bool put_furn(int i, int j);

void expand(int i, int j, bool a[N][N])
{
	for (int x : {i-1, i, i+1}) for (int y : {j-1, j, j+1}) {
		if (x < 0 || n <= x || y < 0 || m <= y)
			continue;
		if (has_furn[x][y] && !a[x][y]) {
			a[x][y] = 1;
			put_furn(x, y);
		}
		a[x][y] = 1;
	}
}
	

bool put_furn(int i, int j)
{
	if (has_a[i][j] && has_b[i][j])
		return 0;
	has_furn[i][j] = 1;
	if (has_a[i][j]) {
		expand(i, j, has_a);
		LoopR (k,0,j) {
			if (has_furn[i][k])
				break;
			put_furn(i, k);
		}
		Loop (k,i+1,n) {
			if (has_furn[k][j])
				break;
			put_furn(k, j);
		}
	}
	if (has_b[i][j]) {
		expand(i, j, has_b);
		Loop (k,j+1,m) {
			if (has_furn[i][k])
				break;
			put_furn(i, k);
		}
		LoopR (k,0,i) {
			if (has_furn[k][j])
				break;
			put_furn(k, j);
		}
	}
	return 1;
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n >> m;
	Loop (i,0,n) {
		has_a[i][0] = 1;
		has_b[i][m-1] = 1;
	}
	Loop (j,0,m) {
		has_a[n-1][j] = 1;
		has_b[0][j] = 1;
	}
	Loop (i,0,n) Loop (j,0,m) {
		int x;
		cin >> x;
		if (x)
			put_furn(i, j);
	}
	int q;
	cin >> q;
	while (q--) {
		int i, j;
		cin >> i >> j;
		cout << put_furn(i-1, j-1) << '\n';
	}
}

• Subtask 1: 5 / 5
• Subtask 2: 95 / 95