Submission #69089

#	Time	Username	Problem	Language	Result	Execution time	Memory
69089		MatheusLealV	Portals (BOI14_portals)	C++17	0 / 100	35 ms	30956 KiB

portals

#include <bits/stdc++.h>
#define N 1050
#define f first
#define s second
using namespace std;
typedef pair<int, int> pii;

int n, m, xo, yo, xi, yi, dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};

int id[N][N], cnt, dist[N*N];

char mat[N][N];

vector<int> grafo[N*N];

int solve(int ini, int fim)
{
	queue<int> fila;

	memset(dist, 0x3f3f3f3f, sizeof dist);

	dist[ini] = 0;

	fila.push(ini);

	while(!fila.empty())
	{
		int x = fila.front();

		fila.pop();

		for(auto v: grafo[x])
		{
			if(dist[v] > dist[x] + 1)
			{
				dist[v] = dist[x] + 1;

				fila.push(v);
			}
		}
	}

	return dist[fim];
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);

	cin>>n>>m;

	for(int i = 0; i <= n + 1; i++)
		for(int j = 0; j <= m + 1; j++)
			id[i][j] = ++ cnt;

	for(int i = 0; i <= n + 1; i++)
		for(int j = 0; j <= m + 1; j++)
		{
			int x = id[i][j];

			for(int p = 0; p < 4; p++)
			{
				int a = i + dx[p], b = j + dy[p];

				if(a < 0 or b < 0 or a > n + 1 or b > m + 1) continue;

				grafo[x].push_back(id[a][b]); 
			}

			if(!i or i == n + 1 or !j or j == m + 1)
			{
				mat[i][j] = '#';

				continue;
			}

			cin>>mat[i][j];

			if(mat[i][j] == 'S') xo = i, yo = j;

			else if(mat[i][j] == 'C') xi = i, yi = j;
		}

	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= m; j++)
		{
			if(mat[i][j] == '#') continue;

			if(mat[i][j + 1] == '#')
			{
				for(int z = j - 1; z > 0; z--)
				{
					if(mat[i][z - 1] == '#' and mat[i][z] != '#')
					{
						grafo[id[i][j]].push_back(id[i][z]);

						break;
					}
				}
			}

			if(mat[i][j - 1] == '#')
			{
				for(int z = j + 1; z <= m; z ++)
				{
					if(mat[i][z + 1] == '#' and mat[i][z] != '#')
					{
						grafo[id[i][j]].push_back(id[i][z]);

						break;
					}
				}
			}

			if(mat[i - 1][j] == '#')
			{
				for(int z = i + 1; z <= n; z ++)
				{
					if(mat[z + 1][j] == '#' and mat[z][j] != '#')
					{
						grafo[id[i][j]].push_back(id[z][j]);

						break;
					}
				}
			}

			if(mat[i + 1][j] == '#')
			{
				for(int z = i - 1; z > 0; z --)
				{
					if(mat[z - 1][j] == '#' and mat[z][j] != '#')
					{
						grafo[id[i][j]].push_back(id[z][j]);

						break;
					}
				}
			}
		}
	}

	cout<<solve(id[xo][yo], id[xi][yi])<<"\n";
}

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