Submission #2070443
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;
}
//直接行った場合にスコアが最高のエサの位置を調べる
pair<int, int> check_best_pos(const vector<vector<int>>& dist)
{
int 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]];
int tmpScore = food[i][2] - food[i][3] * tmpDist;
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(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 |
B - Food Collector |
User |
toma25 |
Language |
C++14 (GCC 5.4.1) |
Score |
5656 |
Code Size |
6422 Byte |
Status |
AC |
Exec Time |
9 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 |
512 / 20000 |
887 / 20000 |
485 / 20000 |
270 / 20000 |
533 / 20000 |
694 / 20000 |
608 / 20000 |
572 / 20000 |
288 / 20000 |
807 / 20000 |
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 |
6 ms |
256 KB |
subtask_01_02.txt |
AC |
9 ms |
384 KB |
subtask_01_03.txt |
AC |
8 ms |
256 KB |
subtask_01_04.txt |
AC |
7 ms |
256 KB |
subtask_01_05.txt |
AC |
7 ms |
256 KB |
subtask_01_06.txt |
AC |
8 ms |
384 KB |
subtask_01_07.txt |
AC |
8 ms |
384 KB |
subtask_01_08.txt |
AC |
7 ms |
256 KB |
subtask_01_09.txt |
AC |
6 ms |
256 KB |
subtask_01_10.txt |
AC |
7 ms |
384 KB |