oj.uz

Submission #499372

# Submission time Handle Problem Language Result Execution time Memory
499372 2021-12-28T07:09:35 Z jansenkenpegrasio Portals (BOI14_portals) C++14
31 / 100
 1000 ms 1172 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);
		}
	}
//  Tembok arah bawah
	vector <vector <int> > bawah(R, vector <int>(C, -1));
	for (int i = 0; i < C; i++)
	{
		int index = R;
		for (int j = R - 1; j >= 0; j--)
		{
			if (board[j][i] == '#')
				index = j;
			bawah[j][i] = index;
//			printf("i j index %d %d %d\n", i, j, index);
		}
	}
//	printf("Bawah\n");
//	for (int i = 0; i < R; i++)
//	{
//		for (int j = 0; j < C; j++)
//		{
//			printf("%d ", bawah[i][j]);
//		}
//		printf("\n");
//	}
// 	Tembok Arah Atas
	vector <vector <int> > atas(R, vector <int>(C, -1));
	for (int i = 0; i < C; i++)
	{
		int index = -1;
		for (int j = 0; j < R; j++)
		{
			if (board[j][i] == '#')
				index = j;
			atas[j][i] = index;
//			printf("i j index %d %d %d\n", i, j, index);
		}
	}
//	printf("Atas\n");
//	for (int i = 0; i < R; i++)
//	{
//		for (int j = 0; j < C; j++)
//		{
//			printf("%d ", atas[i][j]);
//		}
//		printf("\n");
//	}
	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 && distance[x + 1][y] > weight + 1)
		{
			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 && distance[x][y + 1] > weight + 1)
		{
			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 && distance[x - 1][y] > weight + 1)
		{
			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 && distance[x][y - 1] > weight + 1)
		{
			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 = bawah[x][y]; // inget x itu berhubungannya dengan baris
		if (distance[temp_x - 1][y] > weight + tembok[x][y])
		{
			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 = atas[x][y];
//		printf("Atas\n");
		if (distance[temp_x + 1][y] > weight + tembok[x][y])
		{
			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");
		if (distance[x][temp_y - 1] > weight + tembok[x][y])
		{
			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");
		if (distance[x][temp_y + 1] > weight + tembok[x][y])
		{
			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 204 KB Output is correct
2 Correct 0 ms 276 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 276 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 93 ms 352 KB Output is correct
10 Correct 55 ms 336 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 22 ms 340 KB Output is correct
13 Correct 50 ms 332 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 24 ms 332 KB Output is correct
16 Correct 0 ms 204 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 276 KB Output is correct
5 Correct 58 ms 1100 KB Output is correct
6 Execution timed out 1090 ms 1104 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 276 KB Output is correct
9 Correct 91 ms 352 KB Output is correct
10 Correct 55 ms 332 KB Output is correct
11 Correct 1 ms 280 KB Output is correct
12 Correct 23 ms 340 KB Output is correct
13 Correct 51 ms 292 KB Output is correct
14 Correct 56 ms 1112 KB Output is correct
15 Execution timed out 1097 ms 1172 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 216 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 296 KB Output is correct
7 Correct 0 ms 208 KB Output is correct
8 Correct 0 ms 208 KB Output is correct
9 Correct 99 ms 360 KB Output is correct
10 Correct 57 ms 332 KB Output is correct
11 Correct 1 ms 276 KB Output is correct
12 Correct 22 ms 340 KB Output is correct
13 Correct 52 ms 332 KB Output is correct
14 Correct 57 ms 1100 KB Output is correct
15 Execution timed out 1085 ms 1168 KB Time limit exceeded
16 Halted 0 ms 0 KB -