제출 #876378

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
876378		vjudge1	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	1198 ms	167200 KiB

tracks

#include <bits/stdc++.h>
using namespace std;

const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};
const int MAXN = 4000 + 5;
int g[MAXN][MAXN];
int n, m;

int hsh(int i, int j)
{
	return (i * m) + j;
}

int main()
{
	cin >> n >> m;
	bool visited[n][m];
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			char ch;
			cin >> ch;
			if (ch == '.')
				g[i][j] = 0;
			if (ch == 'R')
				g[i][j] = 1;
			if (ch == 'F')
				g[i][j] = 2;
			visited[i][j] = false;
		}
	}
	vector<int> dx = {0, 1, 0, -1};
	vector<int> dy = {1, 0, -1, 0};
	int mxn = hsh(n - 1, m - 1);
	vector<int> dd(mxn + 1, 1e9);
	deque<pair<int, int>> q;
	q.push_front({0, 0});
	dd[0] = 1;
	int ans = 0;
	while (!q.empty())
	{
		pair<int, int> v = q.front();
		int vhsh = hsh(v.first, v.second);
		q.pop_front();
		ans = max(ans, dd[vhsh]);
		if (visited[v.first][v.second])
			continue;
		visited[v.first][v.second] = true;
		int r = v.first;
		int c = v.second;
		for (int k = 0; k < 4; k++)
		{
			int rr = r + dx[k];
			int cc = c + dy[k];
			if (rr < 0 || rr >= n || cc < 0 || cc >= m)
				continue;
			if (visited[rr][cc])
				continue;
			if (g[rr][cc] == 0)
				continue;
			int khsh = hsh(rr, cc);
			if (dd[vhsh] + (g[r][c] != g[rr][cc]) < dd[khsh])
			{
				dd[khsh] = dd[vhsh] + (g[r][c] != g[rr][cc]);
				if (g[rr][cc] != g[r][c])
					q.push_back({rr, cc});
				else
					q.push_front({rr, cc});
			}
		}
	}
	return cout << ans, 0;
	//Olampiad ye tale bood
}

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