Submission #595526

#	Time	Username	Problem	Language	Result	Execution time	Memory
595526		Zian_Jacobson	Mecho (IOI09_mecho)	C++17	62 / 100	1084 ms	10224 KiB

mecho

#include<bits/stdc++.h>
using namespace std;
#define cIO ios_base::sync_with_stdio(0);cin.tie(0)
#define fileIO(x) ifstream fin(string(x)+".in"); ofstream fout(string(x)+".out")
#define ll long long
#define coor pair<int,int>
#define row first
#define col second
#define sz(x) (int) (x).size()
#define v vector
#define f first
#define s second
#define pb push_back
#define at(arr, loc) arr[loc.first][loc.second]
int N, S;//size of map and maximum number of steps Mecho can take
int mr, mc, dr, dc;//row and colums of Mecho and his home

string forest[802];//the map of the forest
int d_to_H[802][802];//minimum distance of grass tile to hive, times S
int steps_M[802][802];//minimum, how many steps it takes for Mecho to get to a tile
int steps_rest[802][802];//minimum, how many STEPS Mecho can eat honey for so that he can still get to the tile before the bees
queue<coor> bfs_H;//bfs for hive
queue<coor> bfs_M;

string filler;//"TTTTT...T"
int rd[] = { 1,0,-1,0 }, cd[] = { 0,1,0,-1 };//delta r and c for a move

void debug(string name, int x)
{
	cout << name << ": " << x << "\n";
}
void debug(string name, coor x)
{
	cout << name << ": " << x.row << "," << x.col << "\n";
}
int main()
{
	for (int i = 0; i <= 801; i++)
	{
		fill_n(d_to_H[i], 802, INT_MAX - 5);
		fill_n(steps_M[i], 802, INT_MAX - 5);
		fill_n(steps_rest[i], 802, 0);
	}
	//input
	cIO;
	cin >> N >> S;
	for (int i = 0; i <= N + 1; i++) filler += "T";
	forest[0] = forest[N + 1] = filler;
	for (int i = 1; i <= N; i++)
	{
		cin >> forest[i];
		forest[i] = string("T") + forest[i] + string("T");
		for (int j = 1; j <= N; j++)
		{
			if (forest[i][j] == 'M') 
			{ 
				mr = i; mc = j; 
				bfs_M.push({ i,j });
				steps_M[i][j] = 0;
				steps_rest[i][j] = INT_MAX - 5;
			}//Mecho's location
			else if (forest[i][j] == 'D') { dr = i; dc = j; }
			else if (forest[i][j] == 'H')
			{
				bfs_H.push({ i,j });
				d_to_H[i][j] = 0;
			}
		}
	}

	//compute d_to_H
	while (!bfs_H.empty())
	{
		coor cur = bfs_H.front(); bfs_H.pop();
		
		for (int i = 0; i <= 3; i++)
		{
			coor move;//next time, bees will try to move here (x4 cause 4 directions)
			move.row = cur.row + rd[i];
			move.col = cur.col + cd[i];
			
			if (at(forest, move)=='G' && at(d_to_H, cur) + S < at(d_to_H, move))//if bees can move there, try
			{
				at(d_to_H, move) = at(d_to_H, cur) + S;
				bfs_H.push(move);
			}
		}
	}

	//bfs on Mecho
	while (!bfs_M.empty())
	{
		coor cur = bfs_M.front(); bfs_M.pop();
		int next_st = at(steps_M, cur) + 1;
		//debug("cur", cur);
		for (int i = 0; i <= 3; i++)
		{
			coor move;//next time, bees will try to move here (x4 cause 4 directions)
			move.row = cur.row + rd[i];
			move.col = cur.col + cd[i];
			//debug("move", move);
			if (at(forest, move) == 'G' 
				|| at(forest, move) == 'D')//whether moving onto it is allowed
				if (min(at(d_to_H, move) - 1 - next_st, at(steps_rest, cur)) > at(steps_rest, move)
					&& next_st < at(d_to_H, move)
					)//whether has more rest than current route, and can reach before bees 
				{
					at(steps_M, move) = next_st;
					at(steps_rest, move) = min(at(d_to_H, move) - 1 - next_st, at(steps_rest, cur));
					//debug("d_to_H[move]", at(d_to_H, move));
					//debug("steps_M[move]", at(steps_M, move));
					//debug("steps_rest[move]", at(steps_rest, move));
					bfs_M.push(move);
				}
		}
	}
	if (at(steps_rest, coor(dr, dc)) == INT_MAX - 5)
		cout << "-1\n";
	else cout << at(steps_rest, coor(dr, dc))/S << "\n";
	return 0;
}

• Subtask 1: 62 / 100