oj.uz

Submission #115732

# Submission time Handle Problem Language Result Execution time Memory
115732 2019-06-08T19:44:04 Z pamaj Portal (COCI17_portal) C++14
96 / 120
 48 ms 5676 KB 
#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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 640 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 640 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 640 KB Output is correct
2 Correct 2 ms 640 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 640 KB Output is correct
2 Correct 2 ms 640 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 640 KB Output is correct
2 Correct 2 ms 640 KB Output is correct
3 Correct 2 ms 640 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 2048 KB Output is correct
2 Correct 4 ms 1536 KB Output is correct
3 Correct 6 ms 1536 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 2048 KB Output is correct
2 Correct 7 ms 2560 KB Output is correct
3 Correct 7 ms 1792 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 4480 KB Output is correct
2 Correct 21 ms 3072 KB Output is correct
3 Correct 15 ms 3584 KB Output is correct

Subtask #9
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 4992 KB Output is correct
2 Correct 21 ms 5632 KB Output is correct
3 Correct 22 ms 3584 KB Output is correct
4 Incorrect 26 ms 4608 KB Output isn't correct

Subtask #10
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 48 ms 5676 KB Output isn't correct
2 Halted 0 ms 0 KB -