Submission #2075903
Source Code Expand
//得点計算←8個のマスの積 //全部9←9^8=81^4≒6400^2≒4000万?←めっちゃでかい //でかい整数くっつければええやん // ↑ //例えば9 ← だったら、9を中心として、マインスイーパーみたいにすると良いんじゃない? //9を中心として、残り7個のマスを近くから選んで、ピースを作る #include<iostream> #include <list> #include<stack> #include<queue> #include <vector> #include <set> #include<algorithm> #include<math.h> #include<stdlib.h> #include<string> #include <functional> using namespace std; //#define PII pair<int,int>←やっぱ分かりにくくなるのでボツ //言い方 //まとめて消すって言ってたけど、 //サイトの方ではピースを作るっていう感じやし、 //今後は「マスを使って、ピースを作る」という感じで話そうな //方針 どうしよ・・・ //スコア←ピースが含む8つの数字の積 //つまり、全部1→1点 // 全部9→9^8=81^4≒6400^2≒4000万点 つきとすっぽんっちゅーわけか //なら、9を中心として、沢山でかいやつを繋げていけばええな //でかいやつとでかいやつを繋げれば、絶対やべぇやつ出来るやろ4000万点みたいな //(まぁ1万で割るから、結局は4000点になるけど) //入力内容 int H, W;//グリッドの大きさ int K; //1つのピースが含める、マスの個数 vector<vector<int>> grid;//グリッドの情報 //出力内容 vector<vector<pair<int, int>>> answer;//答えの情報を格納する //入力を受け付ける関数--akane void input() { //入力1行目 cin >> H >> W >> K; //入力2行目 string str; for (int i = 0; i < H; i++) { vector<int> tmpV; cin >> str; for (int j = 0; j < W; j++) { //string型から1文字だけ取り出すと、char型になるんや。 //詳しくはasciiコードっちゅーやつでググってな tmpV.push_back(str[j] - '0'); } grid.push_back(tmpV); } } //あるピースの、次の1マスを選んで、その座標を返す関数 //選び方は、ピースに縦か横で隣り合ってるマスのうち、最大値をとるやつ //Q:ピースの上下左右を見るために必要なのは? //A:①ピースの位置 ②どこが使えるか ③各マスの数字←global変数 pair<int, int> find_next_square(vector<pair<int, int>> piece, vector<vector<bool>> used) { //めんどいし、マス→square→sq //最大値をとるマスを見つけるには、この2つに着目せんとな int tmpMax = -1; pair<int, int> tmpMaxSq = make_pair(-1, -1);//これをそのまま返せば、ピースを作れなさそうというフラグになる //めんどいし、毎回ピースの上下左右を見る! for (pair<int, int> sq : piece) { //上を見る if (0 < sq.first) {//そもそも上がある sq.first--;//上に、着目座標をずらす //必要な条件(新しい、ピースに含まれるマスになる条件) //①まだ他のピースに使われてはいない ②数字が他に比べて大きい if (used[sq.first][sq.second] == false && grid[sq.first][sq.second] > tmpMax) { //更新!( ..)φメモメモ used[sq.first][sq.second] = true;//使ったよ! tmpMax = grid[sq.first][sq.second];//次に更新するなら、これよりも大きいやつな! tmpMaxSq = sq;//大きいやつが無かったら、これが答えな! } sq.first++; //元に戻す } //以下ほぼコピペ //下を見る if (sq.first < H - 1) { sq.first++; if (used[sq.first][sq.second] == false && grid[sq.first][sq.second] > tmpMax) { used[sq.first][sq.second] = true; tmpMax = grid[sq.first][sq.second]; tmpMaxSq = sq; } sq.first--; } //左を見る if (0<sq.second) { sq.second--; if (used[sq.first][sq.second] == false && grid[sq.first][sq.second] > tmpMax) { used[sq.first][sq.second] = true; tmpMax = grid[sq.first][sq.second]; tmpMaxSq = sq; } sq.second++; } //右を見る if (sq.second < W - 1) { sq.second++; if (used[sq.first][sq.second] == false && grid[sq.first][sq.second] > tmpMax) { used[sq.first][sq.second] = true; tmpMax = grid[sq.first][sq.second]; tmpMaxSq = sq; } sq.second--; } } return tmpMaxSq; } //ピースを作る関数 ↓この関数内部での変更を、calc内部のusedにも伝えるために必要 void make_piece(int y, int x, vector<vector<bool>>& used) { //実際には、どうやったらええんや? //マインスイーパー(斜め禁止)でやっていけば良くない? vector<pair<int, int>> piece; //新しく作るピースの内容(つまりy-x座標←yを先に出力しなきゃいけないのでy-xだし、 //配列で見ればyが第1引数みたいなもの) //(x,y)はピースとして使われることを( ..)φメモメモ used[y][x] = true; piece.push_back(make_pair(y, x)); //既に1個は決まってるので、残り7個を選ぶ for (int k = 0; k < 7; k++) { //次の1マスを選ぶの、難しそうやしとりあえず外部関数にして放置することでええな? pair<int, int> nextSquare = find_next_square(piece, used); //ピースが作れなさそうなら無視しよう(返り値を-1にすることで、それを示す) if (nextSquare.first == -1)return; //ピースの仲間入り、nextSquareは出来そうですね //では早速そのことを( ..)φメモメモ used[nextSquare.first][nextSquare.second] = true; piece.push_back(nextSquare); } //選び終えたら、答えに含める answer.push_back(piece); } //主な計算をする関数 void calc() { vector<vector<bool>> used(H, vector<bool>(W, false));//既に使っちゃったマスは、二度と使わないようにしようね //9じゃなくてもええんちゃう? for (int k = 9; k > 0; k--) { //全部のマスを探索←全探索 for (int y = 0; y < H; y++) { for (int x = 0; x < W; x++) { //マスの値がk まだ使われてない if (grid[y][x] == k && used[y][x] == false) {//←こっちの方が見やすい //ピースを作る関数 make_piece(y, x, used); } } } } } //出力をする関数--aoi void output() { //ピースの数を出力する cout << (int)answer.size() << endl; //各ピースについて、出力をする for (auto piece : answer) { //各ピースが含むマスの、x-y座標についてそれぞれ出力を行う //square:マス---aoi for (auto square : piece) { //出力フォーマットは(y座標)(スペース)(座標) cout << square.first+1 << " " << square.second+1 << endl; } } } //コマンドプロンプトが勝手に閉じないようにする関数 void debug() { int aoi; cin >> aoi; } int main() { input(); calc(); output(); debug(); return 0; }
Submission Info
Submission Time | |
---|---|
Task | A - Multiple Pieces |
User | toma25 |
Language | C++14 (GCC 5.4.1) |
Score | 778636 |
Code Size | 7250 Byte |
Status | AC |
Exec Time | 21 ms |
Memory | 256 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 | 77030 / 1343058 | 72389 / 1343058 | 77801 / 1343058 | 75811 / 1343058 | 88246 / 1343058 | 75338 / 1343058 | 81427 / 1343058 | 69912 / 1343058 | 80299 / 1343058 | 80383 / 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 | AC | 21 ms | 256 KB |
subtask_01_02.txt | AC | 21 ms | 256 KB |
subtask_01_03.txt | AC | 21 ms | 256 KB |
subtask_01_04.txt | AC | 21 ms | 256 KB |
subtask_01_05.txt | AC | 21 ms | 256 KB |
subtask_01_06.txt | AC | 21 ms | 256 KB |
subtask_01_07.txt | AC | 21 ms | 256 KB |
subtask_01_08.txt | AC | 21 ms | 256 KB |
subtask_01_09.txt | AC | 21 ms | 256 KB |
subtask_01_10.txt | AC | 21 ms | 256 KB |