Solução por Rogério Júnior
Este é um problema simples de Flood Fill, feito com uma única DFS. Se você não conhece algoritmos de Flood Fill, clique aqui para ver a aula do Curso Noic sobre o assunto. Usaremos uma matriz booleana tab para salvarmos o tabuleiro. Os quadrados que guardarem o valor false podem ser pintados, e os que guardarem true, não (são pretos ou já foram pintados). Usaremos, também, o inteiro qtd para guardarmos quantos já foram. Desse modo, quando chamarmos a DFS em um quadrado, devemos verificar primeiro se podemos pintá-lo (se ele está dentro do tabuleiro e se sua posição em tab guarda false), retornando caso isso ocorra. Feito isso, iremos pintá-lo (marcamos sua posição com true na matriz tab e aumentamos o valor de qtd em uma unidade) e percorrer todos os seus vizinhos, chamando a DFS para cada um deles. Na main, basta lermos os valores de n, m, x, y e k, marcarmos com true em tab todos os quadrados pretos, chamarmos a DFS para o quadrado inicial (x, y) e imprimirmos o valor de qtd. 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
| #include <cstdio> | |
| #define MAXN 220 | |
| bool tab[MAXN][MAXN]; | |
| int n, m, x, y, k, qtd; | |
| // DFS | |
| void dfs(int v, int h){ | |
| // se não puder pintar o quadrado, retorno | |
| if(v<1 or v>n or h<1 or h>m or tab[v][h]) return; | |
| // caso contrário, o pinto | |
| tab[v][h]=true; | |
| qtd++; | |
| // e percorro todos os seus vizinhos | |
| for(int i=v-1; i<=v+1; i++) | |
| for(int j=h-1; j<=h+1; j++) | |
| dfs(i, j); // chamando a DFS para cada um deles | |
| } | |
| int main(){ | |
| // leio os valores de n, m, x, y e k | |
| scanf("%d %d %d %d %d", &n, &m, &x, &y, &k); | |
| // para cada quadrado preto | |
| for(int i=1; i<=k; i++){ | |
| // leio suas coordenadas | |
| int a, b; | |
| scanf("%d %d", &a, &b); | |
| // e o marco na matriz | |
| tab[a][b]=true; | |
| } | |
| // chamo a DFS no quadrado inicial | |
| dfs(x, y); | |
| // e imprimo o valor de qtd | |
| printf("%d\n", qtd); | |
| return 0; | |
| } |
Nosso leitor Roger Benet também apresentou uma solução semelhante:
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
| #include <cstdio> | |
| #define MAX 210 | |
| int matrix[MAX][MAX]; | |
| int n,m,k,x,y; | |
| void dfs(int i, int j){ | |
| if(i >= 1 && i <= n && j >= 1 && j <= m){ | |
| if(matrix[i][j] == 0)matrix[i][j] = 1; | |
| if(matrix[i-1][j-1] == 0){ | |
| matrix[i-1][j-1] = 1; | |
| dfs(i-1,j-1); | |
| } | |
| if(matrix[i-1][j] == 0){ | |
| matrix[i-1][j] = 1; | |
| dfs(i-1,j); | |
| } | |
| if(matrix[i-1][j+1] == 0){ | |
| matrix[i-1][j+1] = 1; | |
| dfs(i-1,j+1); | |
| } | |
| if(matrix[i][j-1] == 0){ | |
| matrix[i][j-1] = 1; | |
| dfs(i,j-1); | |
| } | |
| if(matrix[i][j+1] == 0){ | |
| matrix[i][j+1] = 1; | |
| dfs(i,j+1); | |
| } | |
| if(matrix[i+1][j-1] == 0){ | |
| matrix[i+1][j-1] = 1; | |
| dfs(i+1,j-1); | |
| } | |
| if(matrix[i+1][j] == 0){ | |
| matrix[i+1][j] = 1; | |
| dfs(i+1,j); | |
| } | |
| if(matrix[i+1][j+1] == 0){ | |
| matrix[i+1][j+1] = 1; | |
| dfs(i+1,j+1); | |
| } | |
| } | |
| } | |
| int main(){ | |
| scanf("%d %d %d %d %d", &n ,&m, &x, &y, &k); | |
| while(k--){ | |
| int a,b; | |
| scanf("%d %d", &a, &b); | |
| matrix[a][b] = -1; | |
| } | |
| dfs(x,y); | |
| k = 0; | |
| for(int i = 1; i <= n; i++){ | |
| for(int j = 1; j <= m; j++){ | |
| if(matrix[i][j] == 1)k++; | |
| } | |
| } | |
| printf("%d\n",k); | |
| return 0; | |
| } |