oj.uz

Submission #496565

# Submission time Handle Problem Language Result Execution time Memory
496565 2021-12-21T14:41:22 Z jansenkenpegrasio Portals (BOI14_portals) C++14
11 / 100
 1000 ms 784 KB 
#include<stdio.h>
#include<utility>
#include<queue>
using namespace std;
int main()
{
	int R, C;
	scanf("%d%d", &R, &C);
	vector < vector <char> > board (R, vector <char> (C));
	pair <int, int> start, cake;
	vector < vector <int> > tembok(R, vector <int> (C, 1e9));
	for (int i = 0; i < R; i++)
	{
		for (int j = 0; j < C; j++)
		{
			if (i == 0 || i == R - 1 || j == 0 || j == C - 1)
			{
				tembok[i][j] = 1;
			}
		}
	}
	for (int i = 0; i < R; i++)
	{
		for (int j = 0; j < C; j++)
		{
			scanf(" %c", &board[i][j]);
			if (board[i][j] == 'S')
				start = make_pair(i, j);
			if (board[i][j] == 'C')
				cake = make_pair(i, j);
			if (board[i][j] == '#')
				tembok[i][j] = 0;
		}
	}
//	1. Cari untuk setiap titik, jarak terdekat dengan temboknya berapa?
	for (int i = 0; i < R; i++)
	{
		for (int j = 1; j < C; j++)
		{
			tembok[i][j] = min(tembok[i][j], tembok[i][j - 1] + 1);
		}
	}
	for (int i = 1; i < R; i++)
	{
		for (int j = 0; j < C; j++)
		{
			tembok[i][j] = min(tembok[i][j], tembok[i - 1][j] + 1);
		}
	}
	for (int i = 0; i < R; i++)
	{
		for (int j = C - 2; j >= 0; j--)
		{
			tembok[i][j] = min(tembok[i][j], tembok[i][j + 1] + 1);
		}
	}
	for (int i = R - 2; i >= 0; i--)
	{
		for (int j = 0; j < C; j++)
		{
			tembok[i][j] = min(tembok[i][j], tembok[i + 1][j] + 1);
		}
	}
	priority_queue<pair <int, pair <int, int > > > djikstra;
	vector <vector <int> > distance(R, vector <int> (C, 1e9));
//	first -> jarak, second.first -> x, second.second
	djikstra.push(make_pair(0, make_pair(start.first, start.second)));
	distance[start.first][start.second] = 0;
	while (!djikstra.empty())
	{
		int weight = djikstra.top().first;
		int x = djikstra.top().second.first;
		int y = djikstra.top().second.second;
//		printf("wxy %d %d %d\n", weight, x, y);
		djikstra.pop();
		if (x >= R || y >= C || x < 0 || y < 0)
			continue;
//		printf("A");
		if (board[x][y] == '#')
			continue;
//		printf("B");
		if (weight != distance[x][y])
			continue;
//		printf("C\n");
//		1. Kiri kanan atas bawah
		if (x + 1 < R)
		{
			djikstra.push(make_pair(weight + 1, make_pair(x + 1, y)));
			distance[x + 1][y] = min(distance[x + 1][y], weight + 1);
		}
//		printf("91\n");
		if (y + 1 < C)
		{
			djikstra.push(make_pair(weight + 1, make_pair(x, y + 1)));
			distance[x][y + 1] = min(distance[x][y + 1], weight + 1);
		}
//		printf("97\n");
		if (x - 1 >= 0)
		{
			djikstra.push(make_pair(weight + 1, make_pair(x - 1, y)));
			distance[x - 1][y] = min(distance[x - 1][y], weight + 1);
		}
		if (y - 1 >= 0)
		{
			djikstra.push(make_pair(weight + 1, make_pair(x, y - 1)));
			distance[x][y - 1] = min(distance[x][y - 1], weight + 1);
		}
//		printf("106\n");
//		2. Nembak portal biru masuk lewat tembok terdekat
//		a. Arah Bawah
		int temp_x = x; // inget x itu berhubungannya dengan baris
		while (temp_x != R && board[temp_x][y] != '#')
		{
			temp_x++;
		}
		djikstra.push(make_pair(weight + tembok[x][y], make_pair(temp_x - 1, y)));
		distance[temp_x - 1][y] = min(distance[temp_x - 1][y], weight + tembok[x][y]);
//		printf("Bawah");
//		b. Arah atas
		temp_x = x;
		while (temp_x != -1 && board[temp_x][y] != '#')
		{
			temp_x--;
		}
//		printf("Atas\n");
		djikstra.push(make_pair(weight + tembok[x][y], make_pair(temp_x + 1, y)));
		distance[temp_x + 1][y] = min(distance[temp_x + 1][y], weight + tembok[x][y]);
//		c. Arah kanan
		int temp_y = y;
		while (temp_y != C && board[x][temp_y] != '#')
		{
			temp_y++;
		}
//		printf("Kanan\n");
		djikstra.push(make_pair(weight + tembok[x][y], make_pair(x, temp_y - 1)));
		distance[x][temp_y - 1] = min(distance[x][temp_y - 1], weight + tembok[x][y]);
//		d. Arah Kiri
		temp_y = y;
		while (temp_y != -1 && board[x][temp_y] != '#')
		{
			temp_y--;
		}
//		printf("Kiri\n");
		djikstra.push(make_pair(weight + tembok[x][y], make_pair(x, temp_y + 1)));
		distance[x][temp_y + 1] = min(distance[x][temp_y + 1], weight + tembok[x][y]);
	}
	printf("%d\n", distance[cake.first][cake.second]);
}

Compilation message

portals.cpp: In function 'int main()':
portals.cpp:8:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 |  scanf("%d%d", &R, &C);
      |  ~~~~~^~~~~~~~~~~~~~~~
portals.cpp:26:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |    scanf(" %c", &board[i][j]);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 280 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 11 ms 288 KB Output is correct
6 Correct 3 ms 208 KB Output is correct
7 Correct 2 ms 208 KB Output is correct
8 Correct 3 ms 208 KB Output is correct
9 Correct 0 ms 208 KB Output is correct
10 Correct 1 ms 208 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 280 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 280 KB Output is correct
5 Correct 11 ms 284 KB Output is correct
6 Correct 3 ms 208 KB Output is correct
7 Correct 2 ms 284 KB Output is correct
8 Correct 3 ms 208 KB Output is correct
9 Execution timed out 1081 ms 352 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 284 KB Output is correct
4 Correct 11 ms 284 KB Output is correct
5 Execution timed out 1082 ms 784 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 220 KB Output is correct
2 Correct 0 ms 220 KB Output is correct
3 Correct 0 ms 284 KB Output is correct
4 Correct 1 ms 220 KB Output is correct
5 Correct 11 ms 220 KB Output is correct
6 Correct 2 ms 220 KB Output is correct
7 Correct 2 ms 220 KB Output is correct
8 Correct 3 ms 284 KB Output is correct
9 Execution timed out 1093 ms 352 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 220 KB Output is correct
2 Correct 1 ms 220 KB Output is correct
3 Correct 0 ms 220 KB Output is correct
4 Correct 0 ms 220 KB Output is correct
5 Correct 11 ms 296 KB Output is correct
6 Correct 3 ms 220 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 3 ms 220 KB Output is correct
9 Execution timed out 1079 ms 360 KB Time limit exceeded
10 Halted 0 ms 0 KB -