oj.uz

Submission #69113

# Submission time Handle Problem Language Result Execution time Memory
69113 2018-08-20T04:07:37 Z MatheusLealV Portals (BOI14_portals) C++17
0 / 100
 32 ms 30800 KB 
#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], pai[N*N];

pii O[N];

char mat[N][N];

vector<pii> grafo[N*N];

int solve(int ini, int fim)
{
	priority_queue<pii, vector<pii>, greater<pii> > fila;

	memset(dist, 0x3f3f3f3f, sizeof dist);

	dist[ini] = 1;

	fila.push({1, ini});

	while(!fila.empty())
	{
		int x = fila.top().s, d = fila.top().s;

		fila.pop();

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

				//pai[v.f] = x;

				fila.push({dist[v.f], v.f});
			}
		}
	}

	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;

			O[id[i][j]] = {i, j};
		}
	}

	for(int i = 0; i <= n + 1; i++)
		for(int j = 0; j <= m + 1; j++)
		{
			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;

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

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

			if(mat[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;

					 if(mat[a][b] != '#') grafo[x].push_back({id[a][b], 1}); 
				}
			}
		}
	}

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

			vector< pii > pos;

			for(int z = j; z > 0; z--)
			{
				if(mat[i][z] == '#') break;

				if(mat[i][z - 1] == '#' and mat[i][z] != '#')
				{
					pos.push_back({i, z});

					break;
				}
			}

			for(int z = j; z <= m; z ++)
			{
				if(mat[i][z] == '#') break;

				if(mat[i][z + 1] == '#' and mat[i][z] != '#')
				{
					pos.push_back({i, z});

					break;
				}
			}

			for(int z = i; z <= n; z ++)
			{
				if(mat[z][j] == '#') break;

				if(mat[z + 1][j] == '#' and mat[z][j] != '#')
				{
					pos.push_back({z, j});

					break;
				}
			}

			for(int z = i; z > 0; z --)
			{
				if(mat[z][j] == '#') break;

				if(mat[z - 1][j] == '#' and mat[z][j] != '#')
				{
					pos.push_back({z, j});

					break;
				}
			}

			for(int a = 0; a < pos.size(); a++)
			{
				for(int b = a + 1; b < pos.size(); b++)
				{
					int A = abs(i - pos[a].f) + abs(j - pos[a].s), B = abs(i - pos[b].f) + abs(j - pos[b].s);

					int custo = min(A, B) + 1;

					grafo[id[pos[a].f][pos[a].s]].push_back({id[pos[b].f][pos[b].s], custo});

					grafo[id[pos[b].f][pos[b].s]].push_back({id[pos[a].f][pos[a].s], custo});
				}
			}
		}
	}

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

Compilation message

portals.cpp: In function 'int solve(int, int)':
portals.cpp:30:25: warning: unused variable 'd' [-Wunused-variable]
   int x = fila.top().s, d = fila.top().s;
                         ^
portals.cpp: In function 'int main()':
portals.cpp:159:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int a = 0; a < pos.size(); a++)
                   ~~^~~~~~~~~~~~
portals.cpp:161:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int b = a + 1; b < pos.size(); b++)
                        ~~^~~~~~~~~~~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 30584 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 30696 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 30696 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 30708 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 30800 KB Output isn't correct
2 Halted 0 ms 0 KB -