제출 #296119

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
296119		Berted	Furniture (JOI20_furniture)	C++14	100 / 100	395 ms	12260 KiB

furniture

#include <iostream>
#include <queue>
#define pii pair<int, int>
#define fst first
#define snd second
using namespace std;

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

int n, m, Q, ar[1001][1001];
int cnt[2001];
bool tr[1001][1001], bt[1001][1001];

queue<pii> q;
vector<pii> backtrack;

inline bool inGrid(int y, int x) {return 0 <= y && y < n && 0 <= x && x < m;}

inline void clear()
{
	for (auto &x : backtrack) {bt[x.fst][x.snd] = 0;}
	backtrack.clear();
}

inline void BFS(int y, int x)
{
	q.push({y, x}); backtrack.push_back({y, x});
	bt[y][x] = 1; tr[y][x] = 0;
	while (q.size())
	{
		int cntt[2] = {};
		y = q.front().fst, x = q.front().snd; q.pop();
		if (y == 0 && x == 0) continue;
		if (y == n - 1 && x == m - 1) continue;
		//cout << "REBFS " << y << " " << x << "\n";
		for (int i = 0; i < 4; i++)
		{
			if (inGrid(y + dir[i][0], x + dir[i][1]))
			{
				cntt[i / 2] += tr[y + dir[i][0]][x + dir[i][1]];
			}
		}
		if (tr[y][x] && cntt[0] && cntt[1]) {continue;}
		else
		{
			tr[y][x] = 0; cnt[y + x]--;
			for (int i = 0; i < 4; i++)
			{
				if (inGrid(y + dir[i][0], x + dir[i][1]))
				{
					if (!bt[y + dir[i][0]][x + dir[i][1]] && tr[y + dir[i][0]][x + dir[i][1]])
					{
						bt[y + dir[i][0]][x + dir[i][1]] = 1;
						backtrack.push_back({y + dir[i][0], x + dir[i][1]});
						q.push({y + dir[i][0], x + dir[i][1]});
					}
				}
			}
		}
	}
	clear();
}

inline void preCalculate()
{
	bt[0][0] = 1; q.push({0, 0});
	while (q.size())
	{
		int y = q.front().fst, x = q.front().snd; q.pop();
		for (int i = 2; i < 4; i++)
		{
			if (inGrid(y + dir[i][0], x + dir[i][1]) && !bt[y + dir[i][0]][x + dir[i][1]] && !ar[y + dir[i][0]][x + dir[i][1]])
			{
				bt[y + dir[i][0]][x + dir[i][1]] = 1;
				q.push({y + dir[i][0], x + dir[i][1]});
			}
		}
	}
	tr[n - 1][m - 1] = 1; q.push({n - 1, m - 1});
	while (q.size())
	{
		int y = q.front().fst, x = q.front().snd; q.pop();
		cnt[y + x]++;
		for (int i = 0; i < 2; i++)
		{
			if (inGrid(y + dir[i][0], x + dir[i][1]) && bt[y + dir[i][0]][x + dir[i][1]] && !tr[y + dir[i][0]][x + dir[i][1]])
			{
				tr[y + dir[i][0]][x + dir[i][1]] = 1;
				q.push({y + dir[i][0], x + dir[i][1]});
			}
		}
	}
	for (int i = 0; i < n; i++) 
	{
		for (int j = 0; j < m; j++) bt[i][j] = 0;
	}
}

int main()
{
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++) {cin >> ar[i][j];}
	}
	preCalculate();
	cin >> Q;
	for (int i = 0; i < Q; i++)
	{
		int y, x; cin >> y >> x; y--; x--;
		if (!tr[y][x]) {cout << "1\n";}
		else if (cnt[y + x] > 1) {cout << "1\n"; BFS(y, x);}
		else {cout << "0\n";}
	}
	return 0;
}

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