Submission #1166048

---

Source Code Expand

//全探索 + 貪欲
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#define int long long
using namespace std;

typedef pair<int, int> Pos;
typedef pair<int, vector<Pos>> Piece;

//入力
int h, w, k;
int s[50][50];

void input() {
	string str;
	
	cin >> h >> w >> k;
	
	for (int i = 0; i < h; i++) {
		cin >> str;
		for (int j = 0; j < w; j++) {
			s[i][j] = str[j] - '0';
		}
	}
}

//サブ関数
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};

bool is_range(int r, int c) {
	return 0 <= r && r < h && 0 <= c && c < w;
}

//ピース全列挙
bool marked[50][50] = {false};
vector<Piece> pieces;

//(r, c)…今から見る場所がr行c列目, path…今までの経路 (葉で列挙する系)
void search(int r, int c, vector<Pos> &path) {
	marked[r][c] = true;
	path.push_back(Pos(r, c));

	if (path.size() == k) {
		int score = 1;
		for (int i = 0; i < k; i++) {
			score *= s[path[i].first][path[i].second];
		}
		pieces.push_back(Piece(score, path));
		
		path.pop_back();
		marked[r][c] = false;
		return;
	}
	
	for (int i = 0; i < 4; i++) {
		int nr = r + dy[i];
		int nc = c + dx[i];
		if (is_range(nr, nc) && !marked[nr][nc] && s[nr][nc] > 0) {
			search(nr, nc, path);
		}
	}
	
	path.pop_back();
	marked[r][c] = false;
}

//貪欲
vector<Pos> ans;

void greedy() {
	for (int r = 0; r < h; r++) {
		for (int c = 0; c < w; c++) {
			vector<Pos> path;
			if (s[r][c] > 0) {
				search(r, c, path);
			}
		}
	}
	sort(pieces.begin(), pieces.end(), greater<Piece>());
	
	for (int i = 0; i < pieces.size(); i++) {
		vector<Pos> path = pieces[i].second;
		
		bool can_put = true;
		for (int j = 0; j < path.size(); j++) {
			if (marked[path[j].first][path[j].second]) {
				can_put = false;
				break;
			}
		}
		
		if (can_put) {
			for (int j = 0; j < path.size(); j++) {
				ans.push_back(Pos(path[j].first, path[j].second));
				marked[path[j].first][path[j].second] = true;
			}
		}
	}
}

signed main() {
	input();
	greedy();
	
	cout << ans.size() / k << endl;
	for (int i = 0; i < ans.size(); i++) {
		cout << ans[i].first + 1 << " " << ans[i].second + 1 << endl;
	}
	return 0;
}

Submission Info

Judge Result