Submission #238178

#	Time	Username	Problem	Language	Result	Execution time	Memory
238178		MrRobot_28	Portal (COCI17_portal)	C++17	120 / 120	106 ms	10616 KiB

portal

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

signed main() {
//	ios_base::sync_with_stdio(false);
//	cin.tie(NULL);
//	cout.tie(NULL);
	int n,  m;
	cin >> n >> m;
	vector <vector <char> > A(n, vector <char> (m));
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < m; j++)
		{
			cin >> A[i][j];
		}
	}
	vector <vector <vector <pair <int, int> > > > go_to(4, vector <vector <pair <int, int> > > (n, vector <pair <int, int> > (m)));
	int x, y, x1, y1;
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < m; j++)
		{
			if(A[i][j] == 'C')
			{
				x = i;
				y = j;
			}
			if(A[i][j] == 'F')
			{
				x1 = i;
				y1 = j;
			}
			if(A[i][j] != '#')
			{
				if(A[i - 1][j] != '#')
				{
					go_to[0][i][j] = go_to[0][i - 1][j];
				}
				else
				{
					go_to[0][i][j] = {i, j};
				}
				if(A[i][j - 1] != '#')
				{
					go_to[1][i][j] = go_to[1][i][j - 1];
				}
				else
				{
					go_to[1][i][j] = {i, j};
				}
			}
		}
	}
	for(int i = n - 1; i >= 0; i--)
	{
		for(int j = m - 1; j >= 0; j--)
		{
			if(A[i][j] != '#')
			{
				if(A[i + 1][j] != '#')
				{
					go_to[2][i][j] = go_to[2][i + 1][j];
				}
				else
				{
					go_to[2][i][j] = {i, j};
				}
				if(A[i][j + 1] != '#')
				{
					go_to[3][i][j] = go_to[3][i][j +1 ];
				}
				else
				{
					go_to[3][i][j] = {i, j};
				}
			}
		}
	}
	vector <vector <int> > dist(n, vector <int> (m, 1e9));
	dist[x][y] = 0;
	priority_queue<pair <int, pair <int, int> > > s;
	s.push({0, {x, y}});
	while(s.size() != 0)
	{
		pair <int, int> v =s.top().second;
		if(dist[v.first][v.second] != -s.top().first)
		{
			s.pop();
			continue;
		}
		s.pop();
		int xa = v.first;
		int ya = v.second;
		if(xa > 0 && dist[xa - 1][ya] > dist[xa][ya] + 1 && A[xa - 1][ya] != '#')
		{
			dist[xa - 1][ya] = dist[xa][ya] + 1;
			s.push({-dist[xa - 1][ya], {xa - 1, ya}});
		}
		if(ya > 0 && dist[xa][ya - 1] > dist[xa][ya] + 1 && A[xa][ya - 1] != '#')
		{
			dist[xa][ya - 1] = dist[xa][ya] + 1;
			s.push({-dist[xa][ya - 1], {xa, ya - 1}});
		}
		if(xa < n - 1 && dist[xa + 1][ya] > dist[xa][ya] + 1 && A[xa + 1][ya] != '#')
		{
			dist[xa + 1][ya] = dist[xa][ya] + 1;
			s.push({-dist[xa + 1][ya], {xa + 1, ya}});
		}
		if(ya < m - 1 && dist[xa][ya + 1] > dist[xa][ya] + 1 && A[xa][ya + 1] != '#')
		{
			dist[xa][ya + 1] = dist[xa][ya] + 1;
			s.push({-dist[xa][ya + 1], {xa, ya + 1}});
		}
		for(int i = 0; i < 4; i++)
		{
			for(int j = 0; j < 4; j++)
			{
				if(i == j){
					continue;
				}
				int d = fabs(xa - go_to[i][xa][ya].first) + fabs(ya - go_to[i][xa][ya].second) + 1;
				int tox = go_to[j][xa][ya].first;
				int toy = go_to[j][xa][ya].second;
				if(dist[tox][toy] > dist[xa][ya] + d)
				{
					dist[tox][toy] = dist[xa][ya] + d;
					s.push({-dist[tox][toy], {tox, toy}});
				}
			}
		}
	}
	if(dist[x1][y1] == 1e9)
	{
		cout << "nemoguce";
	}
	else
	{
		cout << dist[x1][y1];
	}
    return 0;
}

Compilation message (stderr)

portal.cpp: In function 'int main()':
portal.cpp:133:16: warning: 'y1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  if(dist[x1][y1] == 1e9)
                ^
portal.cpp:133:12: warning: 'x1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  if(dist[x1][y1] == 1e9)
            ^

• Subtask 1: 12 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 12 / 12
• Subtask 6: 12 / 12
• Subtask 7: 12 / 12
• Subtask 8: 12 / 12
• Subtask 9: 12 / 12
• Subtask 10: 12 / 12