Submission #2070485
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;
const int INF = (1 << 20);
/*
第1回実装方針:
現在地を中心とした、各距離を書きまくる。
*/
//サイトの通り
int H, W, K, sr, sc, N;
vector<vector<bool>> canGo;
vector<vector<int>> food;
//自作変数
vector<vector<int>> foodPos;//index:座標 value:food_implのindex
vector<char> answer;
//サブ関数
//入力
void input()
{
cin >> H >> W >> K >> sr >> sc;
sr--; sc--;
string tmpS;
for (int y = 0; y < H; y++) {
vector<bool>tmpV;
cin >> tmpS;
for (int x = 0; x < W; x++) {
tmpV.push_back(tmpS[x] == '.');
}
canGo.push_back(tmpV);
}
for (int y = 0; y < H; y++) {
foodPos.push_back(vector<int>(W, -1));
}
cin >> N;
for (int i = 0; i < N; i++) {
vector<int> tmpV;
int tmpI;
for (int j = 0; j < 4; j++) {
cin >> tmpI;
tmpV.push_back(tmpI);
}
tmpV[0]--;
tmpV[1]--;
food.push_back(tmpV);
foodPos[tmpV[0]][tmpV[1]] = i;
}
}
//行けそう&近そうなら、距離空間を更新
void update_distance(
const pair<int, int>& will,
const pair<int, int>& willNext,
vector<vector<int>>& dist,
queue<pair<int,int>>& candidate)
{
if (canGo[willNext.first][willNext.second] //行けそう
&&
dist[willNext.first][willNext.second] > dist[will.first][will.second] + 1//近そう
)
{
dist[willNext.first][willNext.second] = dist[will.first][will.second] + 1;//距離を更新
candidate.push(willNext);//新たな調査対象とする
}
}
//現在地からの距離を、各マスに対してとりあえず示す(-1は行けないところ)
vector<vector<int>> make_distance(const pair<int,int>& now)
{
//変数宣言
vector<vector<int>> dist(H, vector<int>(W, INF));//現在地からの距離
queue<pair<int, int>> candidate;//探索予定の場所
//初期準備
dist[now.first][now.second] = 0;
candidate.push(now);
//メインの計算(現在地から行ける各位置で、上下左右を見てみる)
while (!candidate.empty()) {
//とりあえず行ける位置を一つ取り出す
auto will = candidate.front(); candidate.pop();
//cout << "L102: "<<will.first << " " << will.second << endl;
//上下左右を見つめて、行けそう&近そうなら距離を更新して、移動候補に入れる
//上
if (0 < will.first) {
auto willNext = will;
willNext.first--;
update_distance(will, willNext, dist,candidate);
}
//下
if (will.first<H-1) {
auto willNext = will;
willNext.first++;
update_distance(will, willNext, dist, candidate);
}
//左
if (0 < will.second) {
auto willNext = will;
willNext.second--;
update_distance(will, willNext, dist, candidate);
}
//右
if (will.second<W-1) {
auto willNext = will;
willNext.second++;
update_distance(will, willNext, dist, candidate);
}
}
return dist;
}
/*
int update_vias(
const int& time,
const vector<int>& will,
const vector<int>& willNext,
vector<vector<bool>>& went,
queue<vector<int>>& candidate)
{
//ヒューリスティック内容
const int near = 5;//近隣と言える距離
if (canGo[willNext[1]][willNext[2]]//行ける
&&
went[willNext[1]][willNext[2]]==false) //行ってない
{
//情報更新
went[willNext[1]][willNext[2]] == true;
if (willNext[0] < near) {
candidate.push(willNext);
}
//vias
int id = foodPos[willNext[1]][willNext[2]];
if (id != -1) {
return (food[id][2]-food[id][3]*time)*0.2*(near-willNext[0]);
}
}
return 0;
}
//近隣に別のエサがあるのであれば、その分スコアを高めに取る
int vias(const int time,const pair<int, int> now, const vector<vector<int>>& dist)
{
//変数
int viasSum=0;
vector<vector<bool>> went(H, vector<bool>(W, false));//移動し終えたところ
queue<vector<int>> candidate;//移動候補
//初期化
went[now.first][now.second] = true;
vector<int> _now;
_now.push_back(0);
_now.push_back(now.first);
_now.push_back(now.second);
candidate.push(_now);
//ひたすら周囲の探索
while (!candidate.empty()) {
vector<int> will = candidate.front(); candidate.pop();
//上は行けそうか
if (0 < will[1]) {
auto willNext = will;
willNext[1]--;
viasSum+=update_vias(time,will,willNext,went,candidate);
}
}
return viasSum;
}
*/
//直接行った場合にスコアが最高のエサの位置を調べる
pair<int, int> check_best_pos(const int time, const vector<vector<int>>& dist)
{
//ヒューリスティック部分
const double vias = -2.0;//遠くなるほど、スコアを低くなるように調整
double bestScore = 0;
pair<int, int> bestPos = make_pair(-1, -1);
for (int i = 0; i < N; i++) {
int tmpDist = dist[food[i][0]][food[i][1]];
double tmpScore = food[i][2] - food[i][3] * (time + tmpDist);
tmpScore *= pow(tmpDist, vias);
//tmpScore += vias(time, make_pair(food[i][0], food[i][1]), dist);
if (bestScore < tmpScore) {
bestScore = tmpScore;
bestPos = make_pair(food[i][0], food[i][1]);
}
}
return bestPos;
}
//エサがあったらついでに獲得する関数
void get_food(pair<int, int> pos)
{
int id = foodPos[pos.first][pos.second];
if (id != -1) {
food[id][2] = -1;
}
}
//bestPosまで移動するルートを検索。後、エサを獲得した処理もしておく
vector<char> make_root_to_best_pos(pair<int, int> bestPos,const vector<vector<int>>& dist) {
//bestPosまでの道順
vector<char> root;
//bestPosのエサも回収
get_food(bestPos);
//現在地に戻るまで続ける
do {
int nowDist = dist[bestPos.first][bestPos.second];
//(bestPosから見て)上に移動すると、現在地に近づくかどうか
if (0 < bestPos.first && dist[bestPos.first - 1][bestPos.second] < nowDist) {
bestPos.first--;
get_food(bestPos);
root.push_back('D');
continue;
}
//下
if (bestPos.first<H-1 && dist[bestPos.first + 1][bestPos.second] < nowDist) {
bestPos.first++;
get_food(bestPos);
root.push_back('U');
continue;
}
//左
if (0 < bestPos.second && dist[bestPos.first][bestPos.second-1] < nowDist) {
bestPos.second--;
get_food(bestPos);
root.push_back('R');
continue;
}
//右
if (bestPos.second<W-1 && dist[bestPos.first][bestPos.second+1] < nowDist) {
bestPos.second++;
get_food(bestPos);
root.push_back('L');
continue;
}
} while (dist[bestPos.first][bestPos.second] > 0);
reverse(root.begin(), root.end());
return root;
}
//計算
void calc()
{
pair<int, int> now = make_pair(sr, sc);
while ((int)answer.size() < 2500) {
//cout << answer.size() << endl;
//まずは距離空間を創っておく
vector<vector<int>> dist = make_distance(now);
//次に、最高スコアを取れるエサの座標を探す
pair<int, int> bestPos = check_best_pos((int)answer.size(), dist);
now = bestPos;
//ロクなエサがもうなさそうなら終了
if (bestPos.first == -1)break;
//bestPosまで移動するルートを検索。後、エサを獲得した処理もしておく
vector<char> root = make_root_to_best_pos(bestPos, dist);
//答えの後ろにくっつけておく
//https://qiita.com/D-3/items/b19b7acb439ed0e3deee
answer.insert(answer.end(), root.begin(), root.end());
}
}
//出力
//http://gin0606.hatenablog.com/entry/2013/12/12/162218
void output()
{
//出力が2500文字丁度らしいので調整しようね
while ((int)answer.size() < 2500) {
answer.push_back('-');
}
while ((int)answer.size() > 2500) {
answer.pop_back();
}
//string型に変更して出力するで
string answerS(answer.begin(), answer.end());
cout << answerS << 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 |
8201 Byte |
Status |
RE |
Exec Time |
97 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 |
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 |
RE |
97 ms |
256 KB |
subtask_01_02.txt |
RE |
97 ms |
256 KB |
subtask_01_03.txt |
RE |
96 ms |
256 KB |
subtask_01_04.txt |
RE |
96 ms |
256 KB |
subtask_01_05.txt |
RE |
96 ms |
256 KB |
subtask_01_06.txt |
RE |
97 ms |
256 KB |
subtask_01_07.txt |
RE |
96 ms |
256 KB |
subtask_01_08.txt |
RE |
97 ms |
256 KB |
subtask_01_09.txt |
RE |
97 ms |
256 KB |
subtask_01_10.txt |
RE |
97 ms |
256 KB |