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 |
|
|
|
|
|
|
|
|
|
|
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 |