Submission #1140766

---

Source Code Expand

#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if (y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if (x < y) x = y; }

class PolyominoEnumeration {
public:
	struct Pos {
		int8_t x, y;
		Pos() : x(0), y(0) {}
		Pos(int x, int y) : x(x), y(y) {}
	};

	struct Polyomino {
		vector<Pos> poses;
		int h, w;
	};

	long long enumerate(int n) {
		H = n;
		W = n * 2 - 1;
		que.resize(H * W);
		placed.resize(n);
		blocked.assign(H * W, false);
		outL = outU = n;
		totalCount = 0;
		for (int x = 0; x < n; ++ x)
			blocked[0 * W + x] = true;
		que[0] = Pos(n - 1, 0);
		result.clear();
		dfs(0, 0, 1);
		return totalCount;
	}

private:
	void dfs(int num, int qh, int qt) {
		for (int i = qh; i < qt; ++ i) {
			Pos pos = que[i];
			placed[num] = pos;
			if (outL <= num + 1 && num + 1 <= outU) {
				int minX = INF, minY = INF;
				int maxX = -INF, maxY = -INF;
				rep(k, num + 1) {
					int x = placed[k].x, y = placed[k].y;
					amin(minX, x);
					amin(minY, y);
					amax(maxX, x);
					amax(maxY, y);
				}
				Polyomino r;
				r.poses.resize(num + 1);
				rep(k, num + 1)
					r.poses[k] = Pos(placed[k].x - minX, placed[k].y - minY);
				r.w = maxX + 1 - minX;
				r.h = maxY + 1 - minY;
				result.push_back(r);
				++ totalCount;
			}
			if (num + 1 < outU) {
				int nqt = qt;
				static const int dy[4] = { 0, 1, 0, -1 }, dx[4] = { 1, 0, -1, 0 };
				for (int d = 0; d < 4; ++ d) {
					int yy = pos.y + dy[d], xx = pos.x + dx[d];
					if (yy < 0 || yy >= H || xx < 0 || xx >= W) continue;
					if (blocked[yy * W + xx]) continue;
					que[nqt ++] = Pos(xx, yy);
				}
				for (int k = qt; k < nqt; ++ k)
					blocked[que[k].y * W + que[k].x] = true;
				dfs(num + 1, i + 1, nqt);
				for (int k = qt; k < nqt; ++ k)
					blocked[que[k].y * W + que[k].x] = false;
			}
		}
	}

	int H, W;
	vector<Pos> que;
	vector<Pos> placed;
	vector<bool> blocked;
	int outL, outU;
	long long totalCount;

public:
	vector<Polyomino> result;
};

struct Placement {
	int prod;
	int pi;
	int i, j;
};

int main() {
	int H; int W; int K;
	while (~scanf("%d%d%d", &H, &W, &K)) {
		vector<vector<int>> board(H, vector<int>(W));
		rep(i, H) {
			char buf[51];
			scanf("%s", buf);
			rep(j, W)
				board[i][j] = buf[j] - '0';
		}
		vector<Placement> placements;
		PolyominoEnumeration pe;
		pe.enumerate(K);
		rep(pi, pe.result.size()) {
			const auto &p = pe.result[pi];
			rer(i, 0, H - p.h) rer(j, 0, W - p.w) {
				int prod = 1;
				rep(k, K)
					prod *= board[i + p.poses[k].y][j + p.poses[k].x];
				if (prod > 0)
					placements.push_back(Placement{ prod, pi, i, j });
			}
		}
		sort(placements.begin(), placements.end(), [](const Placement &a, const Placement &b) {
			return a.prod > b.prod;
		});
		vector<Placement> ans;
		ll totalScore = 0;
		for(auto &&place : placements) {
			const auto &p = pe.result[place.pi];
			int i = place.i;
			int j = place.j;
			bool ok = true;
			rep(k, K)
				ok &= board[i + p.poses[k].y][j + p.poses[k].x] != -1;
			if (!ok) continue;
			ans.push_back(place);
			totalScore += place.prod;
			rep(k, K)
				board[i + p.poses[k].y][j + p.poses[k].x] = -1;
		}
		//cerr << "score = " << totalScore << endl;
		printf("%d\n", (int)ans.size());
		for (auto &&placement : ans) {
			const auto &p = pe.result[placement.pi];
			int i = placement.i;
			int j = placement.j;
			rep(k, K)
				printf("%d %d\n", i + p.poses[k].y + 1, j + p.poses[k].x + 1);
		}
	}
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:105:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
    scanf("%s", buf);
                    ^

Judge Result