Submission #1255422

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255422		arashmemar	Furniture (JOI20_furniture)	C++20	0 / 100	31 ms	49472 KiB

furniture

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1010;

bool tab[maxn][maxn], mark[2][maxn][maxn];
vector <pair <int, int>> ne[2][maxn][maxn];
vector <pair <int, int>> p[2];
pair <int, int> x = {0, 0};
int n, m;
bool s, isp[2][maxn][maxn];

bool dfs(pair <int, int> v, int t, bool cfp = 1)
{
	if (mark[t][v.first][v.second] and s == 0)
	{
		isp[t][p[t].back().first][p[t].back().second] = 0;
		p[t].pop_back();
		s = (v == x);
		mark[t][v.first][v.second] = s;
		dfs(p[t].back(), t, 0);
		return 0;
	}
	mark[t][v.first][v.second] = 1;
	if (v == make_pair(n, m))
	{
		return 1;
	}
	for (auto u : ne[t][v.first][v.second])
	{
		if (mark[t][u.first][u.second])
		{
			continue;
		}
		p[t].push_back(u);
		isp[t][u.first][u.second] = 1;
		if (dfs(u, t))
		{
			return 1;
		}
	}
	isp[t][p[t].back().first][p[t].back().second] = 0;
	p[t].pop_back();
	if (cfp)
	{
		return 0;
	}
	dfs(p[t].back(), t, 0);
	return 0;
}

int main()
{
	cin >> n >> m;
	for (int i = 1;i <= n;i++)
	{
		for (int j = 1;j <= m;j++)
		{
			cin >> tab[i][j];
		}
	}
	for (int i = 1;i < n;i++)
	{
		if (!tab[i][m] and !tab[i + 1][m])
		{
			ne[0][i][m].push_back({i + 1, m});
			ne[1][i][m].push_back({i + 1, m});
		}
		for (int j = 1;j < m;j++)
		{
			if (!tab[n][j] and !tab[n][j + 1])
			{
				ne[0][n][j].push_back({n, j + 1});
				ne[1][n][j].push_back({n, j + 1});
			}

			if (!tab[i][j] and !tab[i][j + 1])
			{
				ne[0][i][j].push_back({i, j + 1});
			}
			if (!tab[i][j] and !tab[i + 1][j])
			{
				ne[0][i][j].push_back({i + 1, j});
			}

			if (!tab[i][j] and !tab[i + 1][j])
			{
				ne[1][i][j].push_back({i + 1, j});
			}
			if (!tab[i][j] and !tab[i][j + 1])
			{
				ne[1][i][j].push_back({i, j + 1});
			}
		}
	}

	p[0].push_back({1, 1});
	p[1].push_back({1, 1});

	dfs({1, 1}, 0);
	dfs({1, 1}, 1);


//	x = {1, 2};
//	s = 0;
//	dfs({n, m}, 0);

	int q;
	cin >> q;
	while (q--)
	{
		cin >> x.first >> x.second;
		if (isp[0][x.first][x.second] and isp[1][x.first][x.second])
		{
			cout << 0 << '\n';
			continue;
		}
		cout << 1 << '\n';
		if (isp[0][x.first][x.second])
		{
			s = 0;
			dfs({n, m}, 0, 0);
		}
		if (isp[1][x.first][x.second])
		{
			s = 0;
			dfs({n, m}, 1, 0);
		}
		mark[0][x.first][x.second] = 1;
		mark[1][x.first][x.second] = 1;
		for (auto o : p[0])
		{
			cout << o.first << ' ' << o.second << ", ";
		}
		cout << endl;
	}
}

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