Submission #2070184

---

Source Code Expand

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

/*
第1回実装方針：
9を中心にピースを創れば多分早いでしょ

第2回実装方針:
9～4を中心にしてみた<-本番でやるならここまでが多分限界

第3回実装方針：
でぃーぷらーにんぐで、評価関数ってものがあった。使ってみよう。
そして、上位から使えるだけ使って、answerに入れよう

第4回実装方針：
上位A個だけ使うのをB回ループさせたらどうなるんだろ
(時間ギリギリを狙う)

第5回実装方針：
4～9までのマス目をコアとして、貪欲にピースを作成。
その中で一番スコアが高いのを答えに含めるのを、ピースが作れなくなるまで続ける
*/

//サイトにある通りの変数
int H, W, K;
vector<vector<int>> s;


//自作変数
vector<pair<int,vector<pair<int, int>>>> candidate;//答えの候補を格納する
vector<vector<pair<int,int>>> answer;//答えを格納する

//サブ関数
//入力
void input()
{
	//入力1行目
	cin >> H >> W >> K;

	//入力2行目以降
	string tmpS;
	for (int i = 0; i < H; i++) {
		vector<int> tmpV;
		cin >> tmpS;
		for (int j = 0; j < W; j++) {
			//注:stringから1文字だけ取り出すと、char型なので
			tmpV.push_back(tmpS[j] - '0');
		}
		s.push_back(tmpV);//お姉ちゃんが忘れちゃったところ
	}
}


//最大値だったら更新する
void update_max_data(
	int& tmpMax,
	pair<int, int>& tmpMaxSq,
	const pair<int, int>& nextSq,
	const vector<vector<bool>>& used
)
{
	if (s[nextSq.first][nextSq.second] > tmpMax && used[nextSq.first][nextSq.second] == false) {
		tmpMax = s[nextSq.first][nextSq.second];
		tmpMaxSq = nextSq;
	}
}

//既にあるpieceに対して縦か横で隣り合ってるマス目のうち、最大値を持つマス目の座標を返す
pair<int, int> find_best_square(const vector<pair<int, int>>& piece, const vector<vector<bool>>& used)
{
	int tmpMax = -1;//付近にあるマス目の暫定的最大値です
	pair<int, int> tmpMaxSq = make_pair(-1, -1);//暫定的最大値の座標です

												//実装面倒くさいので、毎回ピースの各要素の、上下左右見ちゃおう（TLEしたら直す）
	for (auto nextSq : piece) {
		//上
		if (0 < nextSq.first) {//そもそも上がある
			nextSq.first--;//上の座標に調整
			update_max_data(tmpMax, tmpMaxSq, nextSq, used);
			nextSq.first++;//元に戻す
		}
		//以下、上のを少しいじっただけ
		//下
		if (nextSq.first < H - 1) {
			nextSq.first++;
			update_max_data(tmpMax, tmpMaxSq, nextSq, used);
			nextSq.first--;
		}
		//左
		if (0<nextSq.second) {
			nextSq.second--;
			update_max_data(tmpMax, tmpMaxSq, nextSq, used);
			nextSq.second++;
		}
		//右
		if (nextSq.second < W - 1) {
			nextSq.second++;
			update_max_data(tmpMax, tmpMaxSq, nextSq, used);
			nextSq.second--;
		}
	}
	return tmpMaxSq;
}

//点数計算
int calcScore(vector<pair<int,int>> piece) 
{
	int ans = 1;
	for (auto square : piece) {
		ans *= s[square.first][square.second];
	}
	return ans;
}


//座標(x,y)の近くにある、大きい数字が書かれたマスを一緒にして、ピースにしよう
void make_piece(int y, int x,vector<vector<bool>> used) 
{
	//vector<vector<bool>> used(H, vector<bool>(W, false));//今回はローカルに作ります
	vector<pair<int, int>> piece;//新しく作るピースの内容

	//(x,y)は使用することを( ..)φメモメモ
	piece.push_back(make_pair(y, x));
	used[y][x] = true;
	
	//既に1個は決まってるので、残り7個必要です
	for (int i = 0; i < 7; i++) {
		//新しくピースの仲間入りをするマス目の座標です。
		pair<int, int> newSquare = find_best_square(piece,used);

		//ピースが作れなさそうなら無視しよう
		if (newSquare.first == -1)return;

		//仲間入りしたので、( ..)φメモメモ
		piece.push_back(newSquare);
		used[newSquare.first][newSquare.second] = true;
	}

	//ピースが決まったので、候補に入れよう
	candidate.push_back(make_pair(calcScore(piece), piece));
}


//計算
void calc()
{
	vector<vector<bool>> used(H, vector<bool>(W, false));//answerに既に入れちゃったマス目はtrue
	
	//コアが無くなるまでひたすらループ
	while (true) {
		candidate.clear();


			//全部のマス目に着目する
			for (int y = 0; y < H; y++) {
				for (int x = 0; x < W; x++) {
					//マスの積がスコアなんやろ？なら一番大きいやつを中心にピース作ろうや
					if (used[y][x]==false) {
						make_piece(y, x , used);
					}
				}
			}

		//終了条件
		if (candidate.size() == 0)break;

		//一番スコアの高いやつを採用するで
		auto piece = candidate[0];
		for (int i = 1; i < (int)candidate.size(); i++) {
			if (piece.first < candidate[i].first) {
				piece = candidate[i];
			}
		}
		answer.push_back(piece.second);
		for (auto square : piece.second) {
			used[square.first][square.second] = true;
		}
	}
}


//出力
void output()
{
	//ピースの数を出力する
	cout << (int)answer.size() << endl;

	//それぞれのピースについて出力を行う
	for (auto piece : answer) {
		//各ピースに所属するマス目について、それぞれ出力を行う
		for (auto square : piece) {
			//フォーマットは、(y座標)(スペース)(x座標)
			cout << square.first+1 << " " << square.second+1 << endl;
		}
	}
}

//メイン関数
int main()
{
	input();
	calc();
	output();
	int N;
	cin >> N;
	return 0;
}

Submission Info

Judge Result