Submission #115732

#	Time	Username	Problem	Language	Result	Execution time	Memory
115732		pamaj	Portal (COCI17_portal)	C++14	96 / 120	48 ms	5676 KiB

portal

#include <bits/stdc++.h>
#define F first
#define S second

using namespace std;

const int maxn = 510, inf = 1e9;

int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, -1, 1};

typedef pair<int, int> ii;

int n, m, dist[maxn][maxn];
char mat[maxn][maxn];
ii pi, pf;

struct pos
{
	int xi, xf, yi, yf;
} last[maxn][maxn];

struct iii
{
	int d, x, y;

	bool operator<(const iii& o) const
	{
		return d > o.d;
	}
};

void dijkstra(ii x)
{
	for(int i = 1 ; i <= n ; ++i)
	{
		for(int j = 1 ; j <= m ; ++j)
		{
			dist[i][j] = inf;
		}
	}

	priority_queue<iii> row;

	dist[x.F][x.S] = 0;
	row.push({0, x.F, x.S});

	while(!row.empty())
	{
		int d = row.top().d;
		int x = row.top().x;
		int y = row.top().y;
		
		row.pop();

		if(d > dist[x][y]) continue; 

		int D = dist[x][y] + 1;
		for(int i = 0 ; i < 4 ; ++i)
		{
			if(x + dx[i] <= n && x + dx[i] >= 1 && y + dy[i] >= 1 && y + dy[i] <= m && mat[x + dx[i]][y + dy[i]] != '#' && dist[x][y] + 1 < dist[x + dx[i]][y + dy[i]])
			{
				dist[x + dx[i]][y + dy[i]] = dist[x][y] + 1;
				row.push({D, x + dx[i], y + dy[i]});
			}
		}

		int xi = last[x][y].xi;
		int xf = last[x][y].xf;
		int yi = last[x][y].yi;
		int yf = last[x][y].yf;

		if(xi == y - 1)
		{
			if(xf != y + 1 && D < dist[x][xf-1])
			{
				dist[x][xf-1] = D;
				row.push({D, x, xf-1});
			}

			if(yi != x - 1 && D < dist[yi+1][y])
			{
				dist[yi+1][y] = D;
				row.push({D, yi+1, y});
			}

			if(yf != x + 1 && D < dist[yf-1][y])
			{
				dist[yf-1][y] = D;
				row.push({D, yf-1, y});
			} 
		}

		if(xf == y + 1)
		{
			if(xi != y-1 && D < dist[x][xi+1])
			{
				dist[x][xi+1] = D;
				row.push({D, x, xi+1});
			}

			if(yi != x - 1 && D < dist[yi+1][y])
			{
				dist[yi+1][y] = D;
				row.push({D, yi+1, y});
			}

			if(yf != x + 1 && D < dist[yf-1][y])
			{
				dist[yf-1][y] = D;
				row.push({D, yf-1, y});
			} 
		}

		if(yi == x-1)
		{
			if(xi != y-1 && D < dist[x][xi+1])
			{
				dist[x][xi+1] = D;
				row.push({D, x, xi+1});
			}
			if(xf != y + 1 && D < dist[x][xf-1])
			{
				dist[x][xf-1] = D;
				row.push({D, x, xf-1});
			}

			if(yf != x + 1 && D < dist[yf-1][y])
			{
				dist[yf-1][y] = D;
				row.push({D, yf-1, y});
			} 
		}

		if(yf == x+1)
		{
			if(xi != y-1 && D < dist[x][xi+1])
			{
				dist[x][xi+1] = D;
				row.push({D, x, xi+1});
			}
			if(xf != y + 1 && D < dist[x][xf-1])
			{
				dist[x][xf-1] = D;
				row.push({D, x, xf-1});
			}

			if(yi != x - 1 && D < dist[yi+1][y])
			{
				dist[yi+1][y] = D;
				row.push({D, yi+1, y});
			}
		}
	}
}

int main()
{
	cin >> n >> m;

	memset(mat, '#', sizeof mat);

	for(int i = 1 ; i <= n ; ++i)
	{
		for(int j = 1 ; j <= m ; ++j)
		{
			cin >> mat[i][j];

			if(mat[i][j] == 'C') pi = {i, j};
			if(mat[i][j] == 'F') pf = {i, j};
		}
	}

	for(int i = 1 ; i <= n ; ++i)
	{
		int lasth = 0;
		for(int j = 1 ; j <= m ; ++j)
		{
			if(mat[i][j] == '#') lasth = j;
			else last[i][j].xi = lasth;
		}
		
		lasth = 0;

		for(int j = m ; j >= 1 ; --j)
		{
			if(mat[i][j] == '#') lasth = j;
			else last[i][j].xf = lasth;
		}
	}

	for(int i = 1 ; i <= m ; ++i)
	{
		int lasth = 0;

		for(int j = 1 ; j <= n ; ++j)
		{
			if(mat[j][i] == '#') lasth = j;
			else last[j][i].yi = lasth;
		}

		lasth = 0;

		for(int j = n ; j >= 1 ; --j)
		{
			if(mat[j][i] == '#') lasth = j;
			else last[j][i].yf = lasth;
		}
	}

	dijkstra(pi);

	if(dist[pf.F][pf.S] == inf) cout << "nemoguce\n";
	else cout << dist[pf.F][pf.S] << "\n";
	return 0;
}

• 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: 0 / 12
• Subtask 10: 0 / 12