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
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 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 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