제출 #647727

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
647727		Markomafko972	Furniture (JOI20_furniture)	C++14	100 / 100	319 ms	15900 KiB

furniture

#include <bits/stdc++.h>
#define X first
#define Y second
#define pb push_back
#define pii pair<int, int>
typedef long long ll;
using namespace std;

const int MOD = 1e9 + 7;
const ll INF = 1e18;
const int OFF = (1 << 20);

int n, m, p, t, r, s;
int a[1005][1005];
int kol[2005];
queue< pair<int, int> > q;

void bfs(int w) {
	
	while (!q.empty()) {
		int x = q.front().X;
		int y = q.front().Y;
		q.pop();
		
		if (x == 0 && y == 0) continue;
		if (x == n-1 && y == m-1) continue;
		if (a[x][y] == 0) continue;
		
		if ((x-1 >= 0 && a[x-1][y] == 1) || (y-1 >= 0 && a[x][y-1] == 1)) {
			if ((x+1 < n && a[x+1][y] == 1) || (y+1 < m && a[x][y+1] == 1)) continue;
		}
		
		a[x][y] = 0;
		kol[x+y]--;
		
		if (x+1 < n && w == 0) q.push({x+1, y});
		if (y+1 < m && w == 0) q.push({x, y+1});
		if (x-1 >= 0 && w == 1) q.push({x-1, y});
		if (y-1 >= 0 && w == 1) q.push({x, y-1});
	}
	
}

int query(int x, int y) {
	if (a[x][y] == 0) {
		return 1;
	}
	else {
		if (kol[x+y] == 1) {
			return 0;
		}
		else {
			a[x][y] = 0;
			kol[x+y]--;
			
			//postavit sve
			if (x+1 < n) q.push({x+1, y});
			if (y+1 < m) q.push({x, y+1});
			bfs(0);
			if (x-1 >= 0) q.push({x-1, y});
			if (y-1 >= 0) q.push({x, y-1});
			bfs(1);
			
			return 1;
		}
	}
}

int main () {

	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			a[i][j] = 1;
			kol[i+j]++;
		}
	}
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> t;	
			if (t == 1) query(i, j);
		}
	}
	
	cin >> p;
	for (int i = 0; i < p; i++) {
		cin >> r >> s;
		r--, s--;
		cout << query(r, s) << "\n";
	}

	return 0;
}

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