Algorithm


Problem Name: 2 AD-HOC - beecrowd | 2458

Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2458

Setas

 

Por OBI - Olimpíada Brasileira de Informática 2014 BR Brazil

Timelimit: 1

Gabriel é um garoto que gosta muito de um jogo onde há várias letras em um tabuleiro e o jogador precisa rapidamente pisar nas letras corretas, de acordo com as instruções na tela, seguindo uma música. Cansado de vencer, Gabriel inventou um novo jogo: agora temos um tabuleiro quadrado, com N células de cada lado, em que cada célula possui uma seta que aponta para uma das quatro posições vizinhas. O jogador primeiro escolhe uma célula inicial para se posicionar e, quando a música começa, ele deve caminhar na direção para onde a seta em que ele está aponta. Ganha o jogo quem pisar em mais setas corretas durante um período de tempo.

O problema é que Gabriel joga tão rápido que quando a seta atual manda ele sair do tabuleiro, ele segue a orientação, muitas vezes quebrando alguns objetos próximos. Quando isso acontece, dizemos que a célula inicial deste jogo não é segura, pois leva a um caminho que termina fora do tabuleiro. A figura abaixo mostra dois tabuleiros.

Ajude Gabriel: dada a configuração do tabuleiro, determine quantas células são seguras para ele iniciar o jogo.

 

Entrada

 

A primeira linha da entrada contém um inteiro N (1 ≤ N ≤ 500), o tamanho do tabuleiro. Cada uma das N linhas seguintes contém N caracteres, com as direções das setas. As direções válidas são:

  • ‘V’ Aponta para a célula da linha abaixo, na mesma coluna 
  • ‘<’ (sinal menor-que) aponta para a célula à esquerda, na mesma linha 
  • ‘>’ (sinal maior-que) aponta para a célula à direita, na mesma linha 
  • ‘A’ Aponta para a célula da linha acima, na mesma coluna 

 

Saída

 

Seu programa deve produzir um único inteiro, o número de células seguras.

 

 

 

Exemplos de Entrada Exemplos de Saída

3

>>V

AV<

A<>

8

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming


#include <cstdio>
using namespace std;
#define MAXN 550
int n;
char matriz[MAXN][MAXN];
bool visitado[MAXN][MAXN];
int elegivel(int x, int y) {
    if (x  <  0 || y < 0 || x >= n || y >= n || visitado[x][y]) return 0;
    return 1;
}
int dfs(int x, int y) {
    if (!elegivel(x, y)) return 0;
    int retornar = 1;
    visitado[x][y] = true;
    if (elegivel(x - 1, y) && matriz[x - 1][y] == 'V')
        retornar += dfs(x - 1, y);
    if (elegivel(x + 1, y) && matriz[x + 1][y] == 'A')
        retornar += dfs(x + 1, y);
    if (elegivel(x, y - 1) && matriz[x][y - 1] == '>')
        retornar += dfs(x, y - 1);
    if (elegivel(x, y + 1) && matriz[x][y + 1] == ' < ')
        retornar += dfs(x, y + 1);
    return retornar;
}
int main() {
    scanf("%d", &n);
    int resposta = n * n;
    for (int i = 0; i  <  n; i++) scanf("%s", matriz[i]);
    for (int i = 0; i  <  n; i++) {
        if (matriz[0][i] == 'A') resposta -= dfs(0, i);
        if (matriz[i][0] == ' < ') resposta -= dfs(i, 0);
        if (matriz[n - 1][i] == 'V') resposta -= dfs(n - 1, i);
        if (matriz[i][n - 1] == '>') resposta -= dfs(i, n - 1);
    }
    printf("%d\n", resposta);
    return 0;
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
3
>>V
AV<
A<>

Output

x
+
cmd
8
Advertisements

Demonstration


Previous
#2457 Beecrowd Online Judge Solution 2457 Letras Solution in C, C++, Java, Js and Python
Next
#2459 Beecrowd Online Judge Solution 2459 Copa do Mundo Solution in C, C++, Java, Js and Python