Submission #2078621


Source Code Expand

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
using namespace std;

string GRID[50];

struct POINT {
	int x, y;
	POINT(int x=0,int y=0):x(x),y(y){}

	POINT operator+(POINT r) {
		return POINT(x + r.x, y + r.y);
	}
	bool operator<(const POINT& r)const {
		return x + y < r.x + r.y;
	}
};

POINT DIR[4];

class Solver {
	int H, W, K;

	vector<string>GRIDs;
	vector<vector<int>>GRID;
	vector<vector<POINT>>ans;
	vector<vector<char>>used;
	vector<pair<int,POINT>>Kouho;
public:
	void INPUT() {
		cin >> H >> W >> K;
		GRIDs.resize(H);
		for (int i = 0; i < H; i++)cin >> GRIDs[i];
	}

	void INIT() {
		DIR[0] = POINT(-1, 0);
		DIR[1] = POINT(0, 1);
		DIR[2] = POINT(1, 0);
		DIR[3] = POINT(0, -1);

		INPUT();

		GRID.resize(H, vector<int>(W));
		used.resize(H, vector<char>(W));
		for (int i = 0; i < H; i++) {
			for (int j = 0; j < W; j++) {
				char c = GRIDs[i][j];
				GRID[i][j] = c - '0';
				if(c-'0')Kouho.push_back(make_pair(c - '0', POINT(i, j)));
			}
		}
		sort(Kouho.begin(), Kouho.end());
		reverse(Kouho.begin(), Kouho.end());
	}

	void solve() {
		for (int i = 0; i < Kouho.size(); i++) {
			POINT p = Kouho[i].second;

			if (used[p.x][p.y])continue;

			vector<POINT>tmp;

			priority_queue<pair<int,POINT>, vector<pair<int,POINT>>>Q;
			Q.push(Kouho[i]);

			while (Q.size()) {
				POINT q = Q.top().second; Q.pop();

				tmp.push_back(q);
				used[q.x][q.y] = true;

				if (tmp.size() == K)break;

				for (int k = 0; k < 4; k++) {
					POINT nq = q + DIR[k];
					if (OVER(nq))continue;
					if (GRID[nq.x][nq.y] == 0)continue;
					if (used[nq.x][nq.y])continue;

					Q.push(make_pair(GRID[nq.x][nq.y], nq));
				}
			}

			if (tmp.size() == K)ans.push_back(tmp);
			else {
				for (int i = 0; i < tmp.size(); i++) {
					POINT p = tmp[i];
					used[p.x][p.y] = false;
				}
			}
		}
	}

	void OUTPUT() {
		cout << ans.size() << endl;
		for (int i = 0; i < ans.size(); i++) {
			for (int j = 0; j < K; j++) {
				cout << ans[i][j].x << " " << ans[i][j].y << endl;
			}
		}
	}

	bool OVER(POINT p) {
		return p.x < 0 || p.x >= H || p.y < 0 || p.y >= W;
	}

	void run() {
		INIT();
		solve();
		OUTPUT();
	}
};

int main() {
	Solver slv;

	slv.run();
	
	return 0;
}

Submission Info

Submission Time
Task A - Multiple Pieces
User kurenai3110
Language C++14 (Clang 3.8.0)
Score 0
Code Size 2357 Byte
Status WA
Exec Time 6 ms
Memory 512 KB

Judge Result

Set Name test_01 test_02 test_03 test_04 test_05 test_06 test_07 test_08 test_09 test_10
Score / Max Score 0 / 1343058 0 / 1343058 0 / 1343058 0 / 1343058 0 / 1343058 0 / 1343058 0 / 1343058 0 / 1343058 0 / 1343058 0 / 1343058
Status
WA × 1
WA × 1
WA × 1
WA × 1
WA × 1
WA × 1
WA × 1
WA × 1
WA × 1
WA × 1
Set Name Test Cases
test_01 subtask_01_01.txt
test_02 subtask_01_02.txt
test_03 subtask_01_03.txt
test_04 subtask_01_04.txt
test_05 subtask_01_05.txt
test_06 subtask_01_06.txt
test_07 subtask_01_07.txt
test_08 subtask_01_08.txt
test_09 subtask_01_09.txt
test_10 subtask_01_10.txt
Case Name Status Exec Time Memory
subtask_01_01.txt WA 6 ms 512 KB
subtask_01_02.txt WA 6 ms 384 KB
subtask_01_03.txt WA 6 ms 384 KB
subtask_01_04.txt WA 6 ms 384 KB
subtask_01_05.txt WA 6 ms 384 KB
subtask_01_06.txt WA 6 ms 384 KB
subtask_01_07.txt WA 6 ms 384 KB
subtask_01_08.txt WA 6 ms 384 KB
subtask_01_09.txt WA 6 ms 384 KB
subtask_01_10.txt WA 6 ms 384 KB