Solução por Rogério Júnior
Para uma determinada leveza 
, é fácil usarmos uma 
para descobrirmos se existe um caminho com essa leveza que leva da casa inicial à final, bem como definirmos o tamanho do menor dentre estes caminhos. Basta alterarmos o algoritmo comum da para que ela só visite células que tenham valor menor ou igual a .
Desse modo, se testássemos todas as levezas, a primeira que possibilitasse chegar do início ao fim do tabuleiro seria a resposta correta, logo, basta fazermos uma busca binária para descobrirmos qual a menor leveza que funciona!
Se você não conhece a busca binária, clique aqui para ver esta aula no Curso Noic. Se você não conhece a , clique aqui para ver esta aula no Curso Noic.
Segue o código para melhor entendimento:
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; | |
| } |