Solução por Rogério Júnior
Para uma determinada leveza $$p$$, é fácil usarmos uma $$BFS$$ 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 $$BFS$$ para que ela só visite células que tenham valor menor ou igual a $$p$$.
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 $$BFS$$, clique aqui para ver esta aula no Curso Noic.
Segue o código para melhor entendimento:
| // 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; | |
| } |

Comente