Por OBI - Olimpíada Brasileira de Informática 2006 Brazil
A Sra. Bastos é uma elaboradora de passatempos matemáticos e pediu para que você criasse um programa que conseguisse jogar de forma eficiente a sua mais nova criação.
O jogo consiste em um tabuleiro formado por casas dispostas em N linhas por N colunas. Cada casa contém um inteiro não-negativo. No começo do jogo, uma peça é colocada na casa localizada no canto superior esquerdo, ou seja, na posição (1,1). O objetivo do jogo é mover a peça até a casa localizada no canto inferior direito (posição (N,N)) somente movendo um único quadrado para baixo ou para a direita em cada passo. Além disso, a peça não pode ser colocada em nenhum quadrado que contenha o número zero.
O custo do caminho utilizado para percorrer o tabuleiro corresponde ao produto de todos os números das casas percorridos no caminho. A penalidade é definida utilizando a representação decimal do custo, sendo representada pelo número de dígitos zeros, contados da direita para a esquerda, antes do primeiro dígito diferente de zero. Por exemplo, um custo igual a 501000 tem penalidade 3, e um custo igual a 501 tem penalidade zero.
O objetivo do jogo é conseguir chegar à casa (N,N) através de um caminho “otimizado”. Dizemos que o caminho foi otimizado se a penalidade for mínima.
Escreva um programa que, dado um tabuleiro, determine a penalidade do custo otimizado.
A entrada contém um único conjunto de testes, que deve ser lido do dispositivo de entrada padrão (normalmente o teclado). A primeira linha da entrada contém um inteiro N que indica o número de linhas e colunas do tabuleiro (1 ≤ N ≤ 1000). As N linhas seguintes contêm N inteiros I cada (1 ≤ I ≤ 1000000), que representam o valor da casa do tabuleiro naquela posição. Existe pelo menos uma solução possível para todos os casos de teste.
Seu programa deve imprimir, na saída padrão, uma única linha, contendo a penalidade do custo “otimizado”.
Exemplos de Entrada | Exemplos de Saída |
3 |
0 |
3 |
1 |
4 |
2 |