oj.uz

Submission #115726

# Submission time Handle Problem Language Result Execution time Memory
115726 2019-06-08T19:25:47 Z Leonardo_Paes Portal (COCI17_portal) C++11
24 / 120
 98 ms 20728 KB 
#include <bits/stdc++.h>
#define MAXN 510
using namespace std;
typedef pair < int, int > ii;
typedef pair < int, ii > iii;

int n, m, val[MAXN][MAXN], c, f, vist[MAXN*MAXN];
char mat[MAXN][MAXN];

int l[MAXN][MAXN], r[MAXN][MAXN], u[MAXN][MAXN], d[MAXN][MAXN];

vector < int > grafo[MAXN*MAXN];

int bfs()
{
	queue < ii > fila;
	fila.push({c, 0});

	while(fila.size())
	{
		ii u = fila.front();
		fila.pop();
		int v = u.first;
		int d = u.second;

		if(vist[v]) continue;
		vist[v] = d;

		if(v == f) return d;

		for(int i = 0 ; i < grafo[v].size() ; i++)
		{
			int at = grafo[v][i];
			if(!vist[at]) fila.push({at, d+1});
		}
	}

	return -1;
}

int main()
{
	cin >> n >> m;
	int cont = 1;
	for(int i = 1 ; i <= n ; i++)
	{
		for(int j = 1 ; j <= m ; j++)
		{
			cin >> mat[i][j];
			val[i][j] = cont++;
			if(mat[i][j] == 'C') c = cont-1;
			else if(mat[i][j] == 'F') f = cont-1;
		}
	}

	// vizinhos esquerda

	int last =0;

	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			if(mat[i][j]=='#'){
				last=j;
			}
			else{
				if(mat[i+1][j]=='#')l[i][j]=val[i][last+1];
				if(mat[i-1][j]=='#')l[i][j]=val[i][last+1];
				if(mat[i][j+1]=='#')l[i][j]=val[i][last+1];
				if(mat[i][j-1]=='#')l[i][j]=val[i][last+1];
			}
		}
	}

	// vizinhos direita

	for(int i=1; i<=n; i++){
		for(int j=m; j>=1; j--){
			if(mat[i][j]=='#'){
				last=j;
			}
			else{
				if(mat[i+1][j]=='#')r[i][j]=val[i][last-1];
				if(mat[i-1][j]=='#')r[i][j]=val[i][last-1];
				if(mat[i][j+1]=='#')r[i][j]=val[i][last-1];
				if(mat[i][j-1]=='#')r[i][j]=val[i][last-1];
			}
		}
	}

	// vizinhos cima

	for(int j=1; j<=m; j++){
		for(int i=1; i<=n; i++){
			if(mat[i][j]=='#'){
				last=i;
			}
			else{
				if(mat[i+1][j]=='#')u[i][j]=val[last+1][j];
				if(mat[i-1][j]=='#')u[i][j]=val[last+1][j];
				if(mat[i][j+1]=='#')u[i][j]=val[last+1][j];
				if(mat[i][j-1]=='#')u[i][j]=val[last+1][j];
			}
		}
	}


	// vizinhos baixo

	for(int j=1; j<=m; j++){
		for(int i=n; i>=1; i--){
			if(mat[i][j]=='#'){
				last=i;
			}
			else{
				if(mat[i+1][j]=='#')d[i][j]=val[last-1][j];
				if(mat[i-1][j]=='#')d[i][j]=val[last-1][j];
				if(mat[i][j+1]=='#')d[i][j]=val[last-1][j];
				if(mat[i][j-1]=='#')d[i][j]=val[last-1][j];
			}
		}
	}

	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			if(mat[i][j]=='#')continue;
			if(mat[i+1][j]=='.')grafo[val[i][j]].push_back(val[i+1][j]);
			if(mat[i-1][j]=='.')grafo[val[i][j]].push_back(val[i-1][j]);
			if(mat[i][j+1]=='.')grafo[val[i][j]].push_back(val[i][j+1]);
			if(mat[i][j-1]=='.')grafo[val[i][j]].push_back(val[i][j-1]);
			
			if(mat[i+1][j]=='#')
			{
				grafo[val[i][j]].push_back(r[i][j]);
				grafo[val[i][j]].push_back(d[i][j]);
				grafo[val[i][j]].push_back(l[i][j]);
				grafo[val[i][j]].push_back(u[i][j]);
			}
			else if(mat[i-1][j]=='#'){
				grafo[val[i][j]].push_back(r[i][j]);
				grafo[val[i][j]].push_back(d[i][j]);
				grafo[val[i][j]].push_back(l[i][j]);
				grafo[val[i][j]].push_back(u[i][j]);
			}
			else if(mat[i][j+1]=='#'){
				grafo[val[i][j]].push_back(r[i][j]);
				grafo[val[i][j]].push_back(d[i][j]);
				grafo[val[i][j]].push_back(l[i][j]);
				grafo[val[i][j]].push_back(u[i][j]);
			}
			else if(mat[i][j-1]=='#'){
				grafo[val[i][j]].push_back(r[i][j]);
				grafo[val[i][j]].push_back(d[i][j]);
				grafo[val[i][j]].push_back(l[i][j]);
				grafo[val[i][j]].push_back(u[i][j]);
			}
		}
	}


	/*
	int last=0;

	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
		//	cout << i << " " << j << " " << last << endl;
			if(mat[i][j]=='#' and last==j-1){
				//cout << "aqui\n";
				last=j;
				continue;
			}
			else if(mat[i][j]=='#'){
				grafo[val[i][last+1]].push_back(val[i][j-1]);
				grafo[val[i][j-1]].push_back(val[i][last+1]);
				last=j;
			}
		}
		last=0;
	}

	for(int j=1; j<=m; j++){
		for(int i=1; i<=n; i++){
			if(mat[i][j]=='#' and last==i-1){
				last=i;
				continue;
			}
			else if(mat[i][j]=='#'){
				grafo[val[last+1][j]].push_back(val[i-1][j]);
				grafo[val[i-1][j]].push_back(val[last+1][j]);
				last=i;
			}
		}
		last=0;
	}
	*/
	int resp = bfs();

	if(resp == -1) cout << "nemoguce\n";
	else cout << resp << endl;
}

Compilation message

portal.cpp: In function 'int bfs()':
portal.cpp:31:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0 ; i < grafo[v].size() ; i++)
                   ~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 6528 KB Output isn't correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 6528 KB Output isn't correct

Subtask #3
0 / 12.0

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

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6528 KB Output is correct
2 Correct 7 ms 6528 KB Output is correct

Subtask #5
0 / 12.0

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

Subtask #6
0 / 12.0

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

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 10104 KB Output is correct
2 Correct 15 ms 9216 KB Output is correct
3 Correct 18 ms 8832 KB Output is correct

Subtask #8
0 / 12.0

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

Subtask #9
0 / 12.0

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

Subtask #10
0 / 12.0

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