Submission #269720

#	Time	Username	Problem	Language	Result	Execution time	Memory
269720		Lam_lai_cuoc_doi	Portals (BOI14_portals)	C++17	100 / 100	314 ms	38968 KiB

portals

#define NguyenDangQuan the_author
#define my_heart love_you_to_the_moon_and_back

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

bool typetest;
inline void fastIOfileinput()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	typetest = 0;
}

const int N = 1e3 + 3;
const int Inf = 1e9 + 7;
int m, n, xs, ys, xc, yc, d[N][N];
char s[N][N];
int directx[N][N][4], directy[N][N][4];
int x[] = {1, 0, -1, 0}, y[] = {0, 1, 0, -1};
bool ck[N][N];

void Read()
{
	cin >> m >> n;
	fill_n(&s[0][0], N * N, '#');
	for (int i = 1; i <= m; ++i)
		for (int j = 1; j <= n; ++j)
		{
			cin >> s[i][j];
			if (s[i][j] == 'S')
			{
				xs = i;
				ys = j;
			}
			if (s[i][j] == 'C')
			{
				xc = i;
				yc = j;
			}
		}
}

bool Relax(int x, int y, int a, int b, int w)
{
	if (d[a][b] > d[x][y] + w)
	{
		d[a][b] = d[x][y] + w;
		return true;
	}
	return false;
}

int Dijkstra()
{
	struct Tque
	{
		int x, y, w;
		Tque() {}
		Tque(int x, int y, int w)
		{
			this->x = x;
			this->y = y;
			this->w = w;
		}
		bool operator<(const Tque &a) const
		{
			return w > a.w;
		}
		bool Valid()
		{
			return d[x][y] == w;
		}
	};
	priority_queue<Tque> pq;
	fill_n(&d[0][0], N * N, Inf);
	d[xs][ys] = 0;
	pq.push(Tque(xs, ys, 0));
	while (pq.size())
	{
		Tque c = pq.top();
		pq.pop();
		if (!c.Valid() || ck[c.x][c.y])
			continue;
		ck[c.x][c.y] = 1;
		if (c.x == xc && c.y == yc)
			return c.w;
		int maxn = Inf, pos;
		for (int i = 0; i < 4; ++i)
		{
			int a = c.x + x[i],
				b = c.y + y[i];
			if (maxn > abs(c.x - directx[c.x][c.y][i]) + abs(c.y - directy[c.x][c.y][i]))
			{
				maxn = abs(c.x - directx[c.x][c.y][i]) + abs(c.y - directy[c.x][c.y][i]);
				pos = i;
			}
			if (s[a][b] != '#' && !ck[a][b] && Relax(c.x, c.y, a, b, 1))
				pq.push(Tque(a, b, d[a][b]));
		}
		for (int i = 0; i < 4; ++i)
			if (pos != i)
			{
				int a = directx[c.x][c.y][i],
					b = directy[c.x][c.y][i];
				if (s[a][b] != '#' && !ck[a][b] && Relax(c.x, c.y, a, b, maxn + 1))
					pq.push(Tque(a, b, d[a][b]));
			}
	}
}

void Solve()
{
	/// Calculate up and dow
	for (int j = 1; j <= n; ++j)
	{
		int last = 1;
		for (int i = 1; i <= m; ++i)
		{
			if (s[i][j] == '#')
				last = i + 1;
			else
				directx[i][j][0] = last;
			directy[i][j][0] = j;
		}
		last = m;
		for (int i = m; i; --i)
		{
			if (s[i][j] == '#')
				last = i - 1;
			else
				directx[i][j][1] = last;
			directy[i][j][1] = j;
		}
	}
	/// Calculate lef and rig
	for (int i = 1; i <= m; ++i)
	{
		int last = 1;
		for (int j = 1; j <= n; ++j)
		{
			if (s[i][j] == '#')
				last = j + 1;
			else
				directy[i][j][2] = last;
			directx[i][j][2] = i;
		}
		last = n;
		for (int j = n; j; --j)
		{
			if (s[i][j] == '#')
				last = j - 1;
			else
				directy[i][j][3] = last;
			directx[i][j][3] = i;
		}
	}
	cout << Dijkstra();
}

int32_t main()
{
	fastIOfileinput();
	if (typetest)
	{
		int t;
		cin >> t;
		while (t--)
		{
			Read();
			Solve();
		}
	}
	else
	{
		Read();
		Solve();
	}
}

Compilation message (stderr)

portals.cpp: In function 'int Dijkstra()':
portals.cpp:79:23: warning: control reaches end of non-void function [-Wreturn-type]
   79 |  priority_queue<Tque> pq;
      |                       ^~
portals.cpp:106:4: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
  106 |    if (pos != i)
      |    ^~

• Subtask 1: 11 / 11
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 19 / 19
• Subtask 5: 30 / 30