Submission #115746

#	Time	Username	Problem	Language	Result	Execution time	Memory
115746		pamaj	Portal (COCI17_portal)	C++14	96 / 120	52 ms	6008 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], vis[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] && vis[x][y] == 1) continue; 
 		
 		vis[x][y] = 1;

		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