Submission #886643

#	Time	Username	Problem	Language	Result	Execution time	Memory
886643		MongHwa	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	554 ms	131632 KiB

tracks

#include <iostream>
#include <queue>
#include <tuple>
using namespace std;

#define INF 0x7f7f7f7f

string stage[4001];
int status[4001][4001];

int dirx[] = {1, -1, 0, 0};
int diry[] = {0, 0, 1, -1};
deque<pair<int, int>> dq;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int h, w;
	cin >> h >> w;

	int sum = 0;
	for(int i = 0; i < h; i++)
	{
		cin >> stage[i];
		for(int j = 0; j < w; j++)
			status[i][j] = INF;
	}

	int ans = 0;
	status[0][0] = 1;
	dq.push_front({0, 0});
	while(!dq.empty())
	{
		int x, y;
		tie(x, y) = dq.front(); dq.pop_front();
		
		for(int i = 0; i < 4; i++)
		{
			int dx = x + dirx[i];
			int dy = y + diry[i];

			if(dx < 0 || dx >= h || dy < 0 || dy >= w)
				continue;
			if(stage[dx][dy] == '.')
				continue;

			if(stage[dx][dy] == stage[x][y] && status[dx][dy] > status[x][y])
			{
				status[dx][dy] = status[x][y];
				ans = max(ans, status[dx][dy]);
				dq.push_front({dx, dy});
			}
			else if(stage[dx][dy] != stage[x][y] && status[dx][dy] > status[x][y]+1)
			{
				status[dx][dy] = status[x][y]+1;
				ans = max(ans, status[dx][dy]);
				dq.push_back({dx, dy});
			}
		}
	}
	
	cout << ans << '\n';
}

Compilation message (stderr)

tracks.cpp: In function 'int main()':
tracks.cpp:23:6: warning: unused variable 'sum' [-Wunused-variable]
   23 |  int sum = 0;
      |      ^~~

• Subtask 1: 30 / 30
• Subtask 2: 70 / 70