Submission #499393

#	Time	Username	Problem	Language	Result	Execution time	Memory
499393		jansenkenpegrasio	Portals (BOI14_portals)	C++14	100 / 100	286 ms	26320 KiB

portals

#include<stdio.h>
#include<utility>
#include<queue>
#define pp pair<int, pair <int, int> >
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");
//	}
//  Tembok Arah Kiri
	vector <vector <int> > kiri(R, vector <int>(C, -1));
	for (int i = 0; i < R; i++)
	{
		int index = -1;
		for (int j = 0; j < C; j++)
		{
			if (board[i][j] == '#')
				index = j;
			kiri[i][j] = index;
//			printf("i j index %d %d %d\n", i, j, index);
		}
	}
//	printf("Kiri\n");
//	for (int i = 0; i < R; i++)
//	{
//		for (int j = 0; j < C; j++)
//		{
//			printf("%d ", kiri[i][j]);
//		}
//		printf("\n");
//	}
//  Tembok Arah Kanan
	vector <vector <int> > kanan(R, vector <int>(C, -1));
	for (int i = 0; i < R; i++)
	{
		int index = C;
		for (int j = C - 1; j >= 0; j--)
		{
			if (board[i][j] == '#')
				index = j;
			kanan[i][j] = index;
//			printf("i j index %d %d %d\n", i, j, index);
		}
	}
//	printf("kanan\n");
//	for (int i = 0; i < R; i++)
//	{
//		for (int j = 0; j < C; j++)
//			printf("%d ", kanan[i][j]);
//		printf("\n");
//	}
	priority_queue<pp, vector <pp>, greater <pp> > 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 = kanan[x][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 = kiri[x][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 (stderr)

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

• Subtask 1: 11 / 11
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 19 / 19
• Subtask 5: 30 / 30