Dado uma matriz quadrada de dimensão n×n contendo letras, pode existir múltiplas ocorrências da palavra yizhong. A palavra na matriz deve estar posicionada em sequência contínua ao longo de uma direção constante. A busca deve considerar as 8 direções possíveis (horizontal, vertical e diagonais). Como as palavras podem se cruzar e compartilhar letras, o objetivo é gerar uma nova matriz onde todas as letras que não fazem parte de nenhuma ocorrência da palavra-alvo sejam substituídas pelo caractere *, destacando assim as palavras encontradas.

Formato de Entrada

A primeira linha contém um inteiro n (7 ≤ n ≤ 100), representando a dimensão da matriz. As próximas n linhas contêm as n×n letras que compõem a matriz.

Formato de Saída

A saída deve ser a matriz de dimensão n×n, com as letras pertencentes a palavras yizhong impressas e todos os outros caracteres substituídos por *.

Exemplos

Exemplo 1 de Entrada

7
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa

Exemplo 1 de Saída

*******
*******
*******
*******
*******
*******
*******

Exemplo 2 de Entrada

8
qyizhong
gydthkjy
nwidghji
orbzsfgz
hhgrhwth
zzzzzozo
iwdfrgng
yyyygggg

Exemplo 2 de Saída

*yizhong
gy******
n*i*****
o**z****
h***h***
z****o**
i*****n*
y******g

Uma abordagem para resolver este problema é iterar sobre cada célula da matriz. Para cada célula, verifica-se se ela contém o caractere inicial da palavra-alvo ('y'). Se sim, inspeciona-se as 8 direções a partir desta posição para determinar se a sequência completa de 7 caracteres yizhong pode ser formada. Caso afirmativo, todas as posições correspondentes a essa ocorrência da palavra são marcadas. Por fim, uma nova matriz é gerada, imprimindo as letras nas posições marcadas e substituindo as demais por *.

Implementação em C++:

#include <iostream>
#include <vector>
#include <string>
using namespace std;

const int MAX_DIM = 105;
char letterMatrix[MAX_DIM][MAX_DIM];
bool isPartOfWord[MAX_DIM][MAX_DIM];
int dimension;
const string WORD_TO_FIND = "yizhong";

// Offsets para as 8 direções: cima-esquerda, cima, cima-direita, esquerda, direita, baixo-esquerda, baixo, baixo-direita
const int directionRowOffset[] = {-1, -1, -1, 0, 0, 1, 1, 1};
const int directionColOffset[] = {-1, 0, 1, -1, 1, -1, 0, 1};

// Verifica se a palavra completa está presente a partir de (startRow, startCol) na direção 'dirIndex'
bool isWordPresent(int startRow, int startCol, int dirIndex) {
    for (int charIndex = 0; charIndex < WORD_TO_FIND.length(); ++charIndex) {
        int currentRow = startRow + charIndex * directionRowOffset[dirIndex];
        int currentCol = startCol + charIndex * directionColOffset[dirIndex];
        if (currentRow < 0 || currentRow >= dimension || currentCol < 0 || currentCol >= dimension) {
            return false;
        }
        if (letterMatrix[currentRow][currentCol] != WORD_TO_FIND[charIndex]) {
            return false;
        }
    }
    return true;
}

// Marca todas as posições da palavra encontrada
void markWordPositions(int startRow, int startCol, int dirIndex) {
    for (int charIndex = 0; charIndex < WORD_TO_FIND.length(); ++charIndex) {
        int row = startRow + charIndex * directionRowOffset[dirIndex];
        int col = startCol + charIndex * directionColOffset[dirIndex];
        isPartOfWord[row][col] = true;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> dimension;
    for (int row = 0; row < dimension; ++row) {
        cin >> letterMatrix[row];
    }

    // Inicializa a matriz de marcação
    for (int i = 0; i < dimension; ++i) {
        for (int j = 0; j < dimension; ++j) {
            isPartOfWord[i][j] = false;
        }
    }

    // Busca por ocorrências da palavra
    for (int row = 0; row < dimension; ++row) {
        for (int col = 0; col < dimension; ++col) {
            if (letterMatrix[row][col] == WORD_TO_FIND[0]) {
                for (int direction = 0; direction < 8; ++direction) {
                    if (isWordPresent(row, col, direction)) {
                        markWordPositions(row, col, direction);
                    }
                }
            }
        }
    }

    // Gera a saída
    for (int row = 0; row < dimension; ++row) {
        for (int col = 0; col < dimension; ++col) {
            if (isPartOfWord[row][col]) {
                cout << letterMatrix[row][col];
            } else {
                cout << '*';
            }
        }
        cout << '\n';
    }

    return 0;
}

Explicação do Código

• Estruturas de Dados Principais: A matriz letterMatrix armazena a entrada. A matriz booleana isPartOfWord serve como máscara para registrar quais posições fazem parte de uma palavra válida.
• Vetores de Direção: Os arrays directionRowOffset e directionColOffset encapsulam os deslocamentos para as 8 direções, simplificando a navegação na matriz.
• Função isWordPresent: Recebe uma posição inicial e um índice de direção. Calcula as coordenadas dos 7 caracteres subsequentes nessa direção e verifica se estão dentro dos limites da matriz e se correspondem exatamente aos caracteres da WORD_TO_FIND.
• Função markWordPositions: Percorre as mesmas 7 posições verificadas por isWordPresent e marca-as como verdadeiras na matriz booleana isPartOfWord.
• Lógica Principal: Para cada célula da matriz, se o caractere for 'y', testam-se todas as 8 direções. Se a palavra for encontrada em uma direção, suas letras são marcadas. A saída é construída lendo a matriz original e a máscara booleana.

Análise de Complexidade

• Complexidade Temporal: O(n²), onde n é o lado da matriz. Cada uma das n² células é verificada, e para aquelas que iniciam com 'y', são feitas até 8 verificações de comprimento constante (7 caracteres).
• Complexidade Espacial: O(n²), para armazenar a matriz de entrada e a matriz booleana de marcação.