Created
April 5, 2016 00:23
-
-
Save rogerioagjr/861effe429ddadf355f766d00a798fe2 to your computer and use it in GitHub Desktop.
Caminho
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Caminho - Seletiva IOI 2015 | |
// Rogério Júnior | |
// Complexidade - O(n log n) | |
#include <cstdio> | |
#include <queue> | |
#include <cstring> | |
#include <algorithm> | |
using namespace std; | |
#define MAXN 330 | |
#define F first | |
#define S second | |
typedef pair<int,int> ii; | |
int n, tab[MAXN][MAXN]; | |
// BFS que só considera células de valor menor ou igual a leveza | |
int bfs(int leveza, int ini_i=1, int ini_j=1){ | |
queue<ii> fila; | |
int dist[MAXN][MAXN]; | |
// defino as distâncias não visitadas como -1 | |
memset(dist, -1, sizeof dist); | |
// a distância para a célula inicial será 1 | |
//pois o problema pede a quantidade de células no caminho | |
dist[1][1]=1; | |
// coloco a primeira célula no começo da fila | |
fila.push(ii(ini_i,ini_j)); | |
// enquanto a fila não estiver vazia | |
while(!fila.empty()){ | |
// guardo quem está na frente da fila e tiro este elemento dela | |
int i=fila.front().F, j=fila.front().S; | |
fila.pop(); | |
// para cada vizinho da célula que estou olhando | |
int i_=i+1, j_=j; | |
// verifico se ele está nos limites do tabuleiro | |
// se ainda não foi visitdo e se seu valor não supera leveza | |
if(i_>=1 and i_<=n and j>=1 and j<=n and dist[i_][j_]==-1 and tab[i_][j_]<=leveza){ | |
// se todas as condições forem atendidas | |
// sua distância será a distância do pai mais 1 | |
dist[i_][j_]=dist[i][j]+1; | |
// e o adiciono à fila | |
fila.push(ii(i_,j_)); | |
} | |
// repito o mesmo com cada vizinho | |
i_=i-1, j_=j; | |
if(i_>=1 and i_<=n and j>=1 and j<=n and dist[i_][j_]==-1 and tab[i_][j_]<=leveza){ | |
dist[i_][j_]=dist[i][j]+1; | |
fila.push(ii(i_,j_)); | |
} | |
i_=i, j_=j+1; | |
if(i_>=1 and i_<=n and j>=1 and j<=n and dist[i_][j_]==-1 and tab[i_][j_]<=leveza){ | |
dist[i_][j_]=dist[i][j]+1; | |
fila.push(ii(i_,j_)); | |
} | |
i_=i, j_=j-1; | |
if(i_>=1 and i_<=n and j>=1 and j<=n and dist[i_][j_]==-1 and tab[i_][j_]<=leveza){ | |
dist[i_][j_]=dist[i][j]+1; | |
fila.push(ii(i_,j_)); | |
} | |
} | |
// retorno a distância para a célula final | |
return dist[n][n]; | |
} | |
int main(){ | |
// leio a entrada | |
scanf("%d", &n); | |
for(int i=1; i<=n; i++) | |
for(int j=1; j<=n; j++) | |
scanf("%d", &tab[i][j]); | |
// defino os limites da busca binária | |
int ini=1, fim=300; | |
ii resp; | |
// realizo o algoritmo comum da busca binária | |
while(ini<=fim){ | |
// calculo o meio do intervalo | |
int meio=(ini+fim)/2; | |
// a quantidade de célulasno menor caminho com essa leveza | |
// que vai da célula inicial à final do tabuleiro | |
int d=bfs(meio); | |
// se o caminho não existe, a resposta está depois de meio | |
if(d==-1) ini=meio+1; | |
// caso contrário | |
else{ | |
// esta é a melhor resposta encontrada até agora | |
resp=ii(meio, d); | |
// e uma resposta melhor só pode estar antes de meio | |
fim=meio-1; | |
} | |
} | |
// imprimo a melhor resposta encontrada pela busca binária | |
printf("%d %d\n", resp.F, resp.S); | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment