Submission #2078730

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <functional>
using namespace std;

struct POINT {
	int x, y;
	POINT(int x=0,int y=0):x(x),y(y){}

	POINT operator+(POINT r) {
		return POINT(x + r.x, y + r.y);
	}
	bool operator<(const POINT& r)const {
		return x + y < r.x + r.y;
	}
	bool operator==(POINT r) {
		return x == r.x && y == r.y;
	}
	bool operator!=(POINT r) {
		return x != r.x || y != r.y;
	}
};

POINT DIR[4];
char mov[5];

struct FOOD {
	POINT p;
	int F, D;
	int id;

	FOOD(POINT p=POINT(), int F=0, int D=0, int id = -1):p(p),F(F),D(D),id(id){}

	bool operator<(const FOOD& r)const {
		return p < r.p;
	}
};

#define INF 1e9

class Solver {
	int H, W, K;
	POINT sp;

	int N;
	vector<FOOD>food;
	vector<string>GRIDs;
	vector<vector<int>>GRID;
	vector<char>used;

	vector<int>ans;
	vector<vector<int>>status, cost;
public:
	void INPUT() {
		cin >> H >> W >> K;
		cin >> sp.x >> sp.y;
		sp.x--; sp.y--;
		GRIDs.resize(H);
		for (int i = 0; i < H; i++)cin >> GRIDs[i];

		cin >> N;
		food.resize(N);
		for (int i = 0; i < N; i++) {
			cin >> food[i].p.x >> food[i].p.y >> food[i].F >> food[i].D;
			food[i].id = i;
			food[i].p.x--; food[i].p.y--;
		}
	}

	void INIT() {
		DIR[0] = POINT(-1, 0);
		DIR[1] = POINT(0, 1);
		DIR[2] = POINT(1, 0);
		DIR[3] = POINT(0, -1);
		mov[1] = 'D';
		mov[2] = 'L';
		mov[3] = 'U';
		mov[4] = 'R';
		mov[0] = '-';

		INPUT();

		status.resize(H, vector<int>(W));
		cost.resize(H, vector<int>(W));
		GRID.resize(H, vector<int>(W));
		used.resize(N);
		for (int i = 0; i < H; i++) {
			for (int j = 0; j < W; j++) {
				char c = GRIDs[i][j];
				if(c=='#')GRID[i][j] = 1;
			}
		}
	}

	void solve() {
		POINT pos = sp;
		int t = 0;
		while (1) {
			dijkstra(pos);

			vector<pair<int, FOOD>>Kouho;
			for (int i = 0; i < N; i++) {
				if (used[i])continue;

				POINT fp = food[i].p;
				int score = max(0, food[i].F - food[i].D*(t + cost[fp.x][fp.y]));
				if (score) {
					Kouho.push_back(make_pair(score, food[i]));
				}
			}

			if (Kouho.empty()) {
				ans.resize(K);
				break;
			}

			sort(Kouho.begin(), Kouho.end());

			vector<int>ret = pathfind(pos, Kouho.back().second.p);
			for (int i = 0; i < ret.size(); i++)ans.push_back(ret[i]);

			pos = Kouho.back().second.p;

			used[Kouho.back().second.id] = true;
		}
	}

	void OUTPUT() {
		for (int i = 0; i < K; i++)cout << mov[ans[i]];
		cout << endl;
	}

	bool OVER(POINT p) {
		return p.x < 0 || p.x >= H || p.y < 0 || p.y >= W;
	}

	void run() {
		INIT();
		solve();
		OUTPUT();
	}

	void dijkstra(POINT s) {
		for (int i = 0; i < H; i++) {
			for (int j = 0; j < W; j++) {
				status[i][j] = 0;
				cost[i][j] = INF;
			}
		}

		status[s.x][s.y] = 1;
		cost[s.x][s.y] = 0;

		priority_queue < pair<int, POINT>, vector<pair<int, POINT>>, greater<pair<int, POINT>>>Q;
		Q.push(make_pair(cost[s.x][s.y], s));

		while (Q.size()) {
			POINT p = Q.top().second;Q.pop();

			if (status[p.x][p.y] == -1)continue;
			status[p.x][p.y] = -1;

			for (int k = 0; k < 4; k++) {
				POINT np = p + DIR[k];
				if (OVER(np))continue;
				if (status[np.x][np.y] == -1)continue;
				if (GRID[np.x][np.y])continue;
				if (cost[np.x][np.y] <= cost[p.x][p.y] + 1)continue;
				cost[np.x][np.y] = cost[p.x][p.y] + 1;
				status[np.x][np.y] = 1;
				Q.push(make_pair(cost[np.x][np.y], np));
			}
		}
	}

	vector<int>pathfind(POINT from, POINT to) {
		vector<int>ret;
		while (from != to) {
			for (int k = 0; k < 4; k++) {
				POINT np = to + DIR[k];
				if (OVER(np))continue;

				if (cost[np.x][np.y] == cost[to.x][to.y] - 1) {
					to = np;
					ret.push_back(k+1);
					break;
				}
			}
		}

		reverse(ret.begin(), ret.end());
		return ret;
	}
};

int main() {
	Solver slv;

	slv.run();
	
	return 0;
}

Submission Info

Judge Result