Submission #2070462


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 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]
		}
	}
}

//近隣に別のエサがあるのであれば、その分スコアを高めに取る
int vias(const pair<int, int> now, const vector<vector<int>>& dist)
{

	//変数
	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]--;

		}
	}
}
*/


//直接行った場合にスコアが最高のエサの位置を調べる
pair<int, int> check_best_pos(const int time, const vector<vector<int>>& dist) 
{
	//ヒューリスティック部分
	const double vias = 1.5;//遠くなるほど、スコアを低くなるように調整
	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] * (time + tmpDist * vias);
		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 B - Food Collector
User toma25
Language C++14 (GCC 5.4.1)
Score 8137
Code Size 7911 Byte
Status AC
Exec Time 7 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 846 / 20000 669 / 20000 918 / 20000 670 / 20000 918 / 20000 1025 / 20000 623 / 20000 909 / 20000 701 / 20000 858 / 20000
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 5 ms 256 KB
subtask_01_02.txt AC 7 ms 384 KB
subtask_01_03.txt AC 6 ms 256 KB
subtask_01_04.txt AC 5 ms 256 KB
subtask_01_05.txt AC 6 ms 256 KB
subtask_01_06.txt AC 7 ms 384 KB
subtask_01_07.txt AC 6 ms 384 KB
subtask_01_08.txt AC 5 ms 256 KB
subtask_01_09.txt AC 4 ms 256 KB
subtask_01_10.txt AC 6 ms 384 KB