Submission #529230

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <cassert>
#include <cstring>
#include <vector>
#include <valarray>
#include <array>
#include <queue>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <complex>
#include <random>

using namespace std;
typedef long long ll;

const int MW = 11;
const int MH = 11;
const int d4[4][2] = {
	{1, 0},
	{0, 1},
	{-1, 0},
	{0, -1}
};

int w, h, r;
int a;

bool g[MH][MW];

void mark(int x, int y) {
	g[y][x] = !g[y][x];
	for (int i = 0; i < 4; i++) {
		int xx = x + d4[i][0], yy = y + d4[i][1];
		if (!(0 <= xx && xx < w && 0 <= yy && yy < h)) continue;
		g[yy][xx] = !g[yy][xx];
	}
}

bool g2[MH][MW];


int main() {
	cin >> w >> h >> r; r--;
	assert(max(w, h) <= 10);
	cin >> a;
	for (int i = 0; i < a; i++) {
		int y, b;
		cin >> y >> b; y--;
		for (int j = 0; j < b; j++) {
			int x;
			cin >> x; x--;
			g[y][x] = true;	
			g2[y][x] = true;
		}
	}

	for (int t = 0; t < (1<<w); t++) {
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				g[i][j] = g2[i][j];
			}
		}
		vector<int> res;
		for (int j = 0; j < w; j++) {
			if ((t >> j) & 1) {
				if (r == 0) {
					res.push_back(j);
				}
				mark(j, 0);
			}
		}
		for (int i = 1; i < h; i++) {
			for (int j = 0; j < w; j++) {
				if (g[i-1][j]) {
					if (r == i) res.push_back(j);
					mark(j, i);
				}
			}
		}
		bool f = true;
		for (int j = 0; j < w; j++) {
			if (g[h-1][j]) {
				f = false;
				break;
			}
		}
		if (!f) continue;
		cout << res.size();
		for (int d: res) {
			cout << " " << d+1;
		}
		cout << endl;
		return 0;
	}
    return 0;
}

Submission Info

Judge Result