oj.uz

답안 #499374

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
499374 2021-12-28T07:17:31 Z jansenkenpegrasio 포탈들 (BOI14_portals) C++14
31 / 100
 1000 ms 1460 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");
//	}
//  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<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 = 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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 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 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 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 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 63 ms 368 KB Output is correct
10 Correct 37 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 21 ms 332 KB Output is correct
13 Correct 44 ms 344 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 26 ms 332 KB Output is correct
16 Correct 0 ms 204 KB Output is correct

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 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 55 ms 1388 KB Output is correct
6 Execution timed out 1093 ms 1452 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 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 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 63 ms 332 KB Output is correct
10 Correct 36 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 22 ms 356 KB Output is correct
13 Correct 44 ms 344 KB Output is correct
14 Correct 57 ms 1388 KB Output is correct
15 Execution timed out 1089 ms 1328 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 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 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 63 ms 332 KB Output is correct
10 Correct 36 ms 344 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 21 ms 352 KB Output is correct
13 Correct 48 ms 332 KB Output is correct
14 Correct 56 ms 1380 KB Output is correct
15 Execution timed out 1092 ms 1460 KB Time limit exceeded
16 Halted 0 ms 0 KB -