Algorithm
Problem Name: 2 AD-HOC - beecrowd | 2465
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2465
Passa Bolinha
Por OBI - Olimpíada Brasileira de Informática 2014 
Brazil
Timelimit: 1
O professor Miguel desafiou os alunos do colégio onde ele leciona com uma brincadeira que exige muita atenção! No pátio do colégio, os alunos formam um quadrado com N fileiras e N colunas, de modo que a primeira fileira esteja voltada para o norte. Cada um dos N2 alunos segura uma bandeira e tem um número colado na camiseta. Inicialmente, as bandeiras estão abaixadas e os alunos estão voltados para o norte. Todos os alunos têm que seguir exatamente o mesmo comportamento:
- Ao receber a bolinha, levanta sua bandeira e realiza a seguinte ação quatro vezes, em sequência:
– Vira-se 90 graus no sentido horário. Se o colega que ficou à sua frente tiver um número na camiseta maior ou igual ao seu, e estiver com a bandeira abaixada, passa a bolinha ao colega e aguarda que ele lhe devolva a bolinha;
- Devolve a bolinha a quem lhe passou a bolinha inicialmente.
Nesta tarefa, você deve escrever um programa que, dados os números nas camisetas de cada aluno, e a posição do aluno a quem o professor Miguel vai entregar a bolinha, calcule quantas bandeiras estarão levantadas ao final, quando esse aluno devolver a bolinha ao professor. Por exemplo, a parte direita da figura abaixo mostra que sete alunos vão levantar a bandeira se o professor entregar inicialmente a bolinha ao aluno na fileira 3, coluna 1, como indicado na parte esquerda da figura.
Entrada
A primeira linha da entrada contém um inteiro N (1 ≤ N ≤ 100), o número de fileiras (que é igual ao de colunas). A segunda linha contém dois números, I e J (1 ≤ I, J ≤ N), indicando respectivamente, a fileira e a coluna do aluno a quem o professor Miguel entregará a bolinha. As N linhas seguintes contém N inteiros cada uma, indicando os números que estão nas camisetas dos alunos (os números nas camisetas estão entre 1 e 9, inclusive).
Saída
Seu programa deve imprimir apenas uma linha contendo um inteiro, o número de bandeiras que estarão levantadas ao final.
| Exemplos de Entrada | Exemplos de Saída |
|
4 |
7 |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <cstdio>
#define MAXN 102
int matriz[MAXN][MAXN], processado[MAXN][MAXN], n, xo, yo, resp;
void dfs(int x, int y) {
if (processado[x][y]) return;
processado[x][y] = 1;
if (matriz[x + 1][y] >= matriz[x][y]) dfs(x + 1, y);
if (matriz[x - 1][y] >= matriz[x][y]) dfs(x - 1, y);
if (matriz[x][y + 1] >= matriz[x][y]) dfs(x, y + 1);
if (matriz[x][y - 1] >= matriz[x][y]) dfs(x, y - 1);
}
int main() {
scanf("%d %d %d", &n, &xo, &yo);
for (int i = 1; i < = n; i++) {
for (int j = 1; j < = n; j++) {
scanf("%d", &matriz[i][j]);
}
}
dfs(xo, yo);
for (int i = 1; i < = n; i++) {
for (int j = 1; j < = n; j++) {
resp += processado[i][j];
}
}
printf("%d\n", resp);
return 0;
}
Input
3 1
6 7 9 9
1 4 3 5
2 4 5 1
1 3 2 9
Output