Submission #405233

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
405233	2021-05-16T02:23:19 Z	rieyuw	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	752 ms	122748 KB

tracks

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <unordered_set>
#include <set>
#include <map>
#include <unordered_map>
#include <iomanip>
#include <random>
#include <queue>
//#include <fstream>
/*#include <cstdio>
#include <ctime>*/
#include <complex>

using namespace std;

/*Problem:  */

void solve()
{
	
	int n, m;
	cin >> n >> m;
	vector<vector<char>> grid(n, vector<char>(m));
	vector <vector<int>> depth(n, vector<int>(m));
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> grid[i][j];
	

	/*cout << "grid" << endl;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
			cout << grid[i][j];
		cout << endl;
	}*/


	int x[] = {-1, 1, 0, 0 };
	int y[] = { 0, 0, -1, 1 };

	deque<pair<int, int>> deck;
	deck.push_front({ 0, 0 });
	depth[0][0] = 1;


	pair<int, int> trace, neig;
	char ani; int ani_depth;
	int ans = -1;
	while (!deck.empty())
	{
		trace = deck.front(); deck.pop_front();
		ani = grid[trace.first][trace.second];
		ani_depth = depth[trace.first][trace.second];

		ans = max(ans, ani_depth);

		for (int i = 0; i < 4; i++)
		{
			neig.first = trace.first + x[i];
			neig.second = trace.second + y[i];
			if (neig.first < 0 || neig.first >= n
				|| neig.second < 0 || neig.second >= m
				|| depth[neig.first][neig.second] != 0
				|| grid[neig.first][neig.second] == '.')
				continue;

			if (grid[neig.first][neig.second] == ani)
			{
				depth[neig.first][neig.second] = ani_depth;
				deck.push_front(neig);
			}
			else
			{
				depth[neig.first][neig.second] = ani_depth + 1;
				deck.push_back(neig);
			}
		}
	}

	/*cout << "depths" << endl;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
			cout << depth[i][j];
		cout << endl;
	}
	*/



	cout << ans << endl;
}

int main() {
	//freopen("revegetate.in", "r", stdin);
	//freopen("revegetate.out", "w", stdout);
	cin.tie(0);
	ios::sync_with_stdio(0);

	int t = 1;
	//cin >> t;

	while (t--)
		solve();


	return 0;
}

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	1740 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	316 KB	Output is correct
4	Correct	7 ms	1356 KB	Output is correct
5	Correct	4 ms	712 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	1 ms	280 KB	Output is correct
9	Correct	1 ms	324 KB	Output is correct
10	Correct	3 ms	716 KB	Output is correct
11	Correct	3 ms	588 KB	Output is correct
12	Correct	7 ms	844 KB	Output is correct
13	Correct	4 ms	824 KB	Output is correct
14	Correct	3 ms	716 KB	Output is correct
15	Correct	12 ms	1740 KB	Output is correct
16	Correct	14 ms	1740 KB	Output is correct
17	Correct	11 ms	1764 KB	Output is correct
18	Correct	8 ms	1356 KB	Output is correct

Subtask #2

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	844 KB	Output is correct
2	Correct	66 ms	9572 KB	Output is correct
3	Correct	421 ms	94760 KB	Output is correct
4	Correct	107 ms	22596 KB	Output is correct
5	Correct	252 ms	53396 KB	Output is correct
6	Correct	728 ms	107812 KB	Output is correct
7	Correct	3 ms	844 KB	Output is correct
8	Correct	3 ms	844 KB	Output is correct
9	Correct	3 ms	588 KB	Output is correct
10	Correct	2 ms	464 KB	Output is correct
11	Correct	3 ms	844 KB	Output is correct
12	Correct	2 ms	460 KB	Output is correct
13	Correct	61 ms	9568 KB	Output is correct
14	Correct	32 ms	5676 KB	Output is correct
15	Correct	29 ms	6256 KB	Output is correct
16	Correct	26 ms	4112 KB	Output is correct
17	Correct	151 ms	24372 KB	Output is correct
18	Correct	118 ms	23864 KB	Output is correct
19	Correct	105 ms	22356 KB	Output is correct
20	Correct	92 ms	20548 KB	Output is correct
21	Correct	245 ms	55260 KB	Output is correct
22	Correct	249 ms	53316 KB	Output is correct
23	Correct	288 ms	45912 KB	Output is correct
24	Correct	236 ms	53828 KB	Output is correct
25	Correct	584 ms	94576 KB	Output is correct
26	Correct	450 ms	122748 KB	Output is correct
27	Correct	610 ms	112240 KB	Output is correct
28	Correct	751 ms	107864 KB	Output is correct
29	Correct	752 ms	108204 KB	Output is correct
30	Correct	676 ms	107172 KB	Output is correct
31	Correct	580 ms	61128 KB	Output is correct
32	Correct	556 ms	110028 KB	Output is correct