Submission #2070085
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回ループさせたらどうなるんだろ
(時間ギリギリを狙う)
*/
//サイトにある通りの変数
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(H, vector<bool>(W, false));//今回はローカルに作ります
vector<pair<int, int>> piece;//新しく作るピースの内容
//(x,y)は使用することを( ..)φメモメモ
piece.push_back(make_pair(y, x));
//既に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));
}
//既に使われてるマスと被ってたら無視
bool check_over(const vector<pair<int, int>>& piece, const vector<vector<bool>>& used)
{
for (auto square : piece) {
if (used[square.first][square.second]) {
return true;
}
}
return false;
}
//計算
void calc()
{
vector<vector<bool>> used(H, vector<bool>(W, false));//answerに既に入れちゃったマス目はtrue
//ほな次、9じゃないやつもやったらどうなるんやろ
for (int k = 9; k > 6; k--) {
//全部のマス目に着目する
for (int y = 0; y < H; y++) {
for (int x = 0; x < W; x++) {
//マスの積がスコアなんやろ?なら一番大きいやつを中心にピース作ろうや
if (s[y][x] == k) {
make_piece(y, x);
}
}
}
}
//候補をソートして、スコアの高い順に採用するで
sort(candidate.begin(), candidate.end());
for (auto piece : candidate) {
//もし被ってたら無視
if (check_over(piece.second, used))continue;
//被ってないなら採用
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
Submission Time |
|
Task |
A - Multiple Pieces |
User |
toma25 |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
5910 Byte |
Status |
WA |
Exec Time |
10 ms |
Memory |
384 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 |
10 ms |
384 KB |
subtask_01_02.txt |
WA |
10 ms |
384 KB |
subtask_01_03.txt |
WA |
10 ms |
384 KB |
subtask_01_04.txt |
WA |
10 ms |
384 KB |
subtask_01_05.txt |
WA |
10 ms |
384 KB |
subtask_01_06.txt |
WA |
10 ms |
384 KB |
subtask_01_07.txt |
WA |
10 ms |
384 KB |
subtask_01_08.txt |
WA |
10 ms |
384 KB |
subtask_01_09.txt |
WA |
10 ms |
384 KB |
subtask_01_10.txt |
WA |
10 ms |
384 KB |