No desenvolvimento de algoritmos para problemas de grafos, a marcação adequada dos nós visitados é essencial para garantir eficiência. Neste caso, utilizamos busca em largura (BFS) combinada com operações módulo, onde o array vis deve ser marcado no momento exato para evitar complexidade desnecessária.

A estratégia correta é marcar os nós assim que são inseridos na fila, não ao serem removidos. Isso porque, em BFS, a primeira vez que um nó é alcançado já representa o caminho mais curto. Se a marcação ocorrer apenas ao retirar da fila, múltiplas visitas ao mesmo nó podem aumentar o tempo de execução.

// Implementação BFS com marcação imediata
int bfs_otimizado() {
    fila.push({1, 1, a[1][1]});
    visitado[1][1][a[1][1]] = 1;
    while (!fila.empty()) {
        auto no_atual = fila.front();
        int linha = no_atual[0], coluna = no_atual[1], resto = no_atual[2];
        fila.pop();
        if (visitado[linha][coluna][resto]) continue;
        visitado[linha][coluna][resto] = 1;
        for (int direcao = 0; direcao < 4; direcao++) {
            int nova_linha = linha + desloc_x[direcao];
            int nova_coluna = coluna + desloc_y[direcao];
            if (nova_linha < 1 || nova_linha > n || nova_coluna < 1 || nova_coluna > m) continue;
            int novo_resto = (resto + a[nova_linha][nova_coluna]) % modulo;
            if (visitado[nova_linha][nova_coluna][novo_resto]) continue;
            visitado[nova_linha][nova_coluna][novo_resto] = 1;
            distancia[nova_linha][nova_coluna][novo_resto] = distancia[linha][coluna][resto] + 1;
            fila.push({nova_linha, nova_coluna, novo_resto});
        }
    }
    return (distancia[n][m][0] != 0) ? distancia[n][m][0] : -1;
}

Essa abordagem difere do algoritmo de Dijkstra, que utiliza uma fila de prioridade. Em Dijkstra, um nó pode ser inserido múltiplas vezes na fila com diferantes custos, e a marcação ocorre apenas quando ele é removido, garantindo que o custo mínimo seja processado primeiro.

// Algoritmo de Dijkstra para comparação
int dijkstra_modificado() {
    fila_prioridade.push({0, ponto_inicial});
    for (int i = 1; i <= total_nos; i++) visitado[i] = 0, custo_minimo[i] = infinito;
    while (!fila_prioridade.empty()) {
        int custo = -fila_prioridade.top().first, no = fila_prioridade.top().second;
        fila_prioridade.pop();
        if (visitado[no]) continue;
        visitado[no] = 1;
        for (int i = cabecalho[no]; i != -1; i = proximo[i]) {
            int vizinho = aresta[i];
            int novo_custo = peso[i] + custo;
            if (novo_custo < custo_minimo[vizinho]) {
                custo_minimo[vizinho] = novo_custo;
                fila_prioridade.push({-novo_custo, vizinho});
            }
        }
    }
    int maximo = 0;
    for (int i = 1; i <= total_nos; i++) {
        if (custo_minimo[i] != infinito) {
            maximo = max(maximo, custo_minimo[i]);
        }
    }
    return maximo;
}

O código completo para resolver o problema inclui leitura de entrada e tratamento de casos especiais, como quando o módulo é 2, onde o caminho mais curto é simplesmente a distância Manhattan.

// Solução completa
#include <bits/stdc++.h>
using namespace std;

const int MAX_LINHA = 15;
const int MAX_RESTO = 10002;
int linhas, colunas, modulo_entrada;
int grade[MAX_LINHA][MAX_LINHA];
int dist[MAX_LINHA][MAX_LINHA][MAX_RESTO];
int vis[MAX_LINHA][MAX_LINHA][MAX_RESTO];
int desloc_x[] = {-1, 0, 0, 1};
int desloc_y[] = {0, -1, 1, 0};

int bfs_solucao() {
    queue<array<int, 3>> fila_bfs;
    fila_bfs.push({1, 1, grade[1][1]});
    vis[1][1][grade[1][1]] = 1;
    while (!fila_bfs.empty()) {
        auto atual = fila_bfs.front();
        int x = atual[0], y = atual[1], z = atual[2];
        fila_bfs.pop();
        for (int d = 0; d < 4; d++) {
            int nx = x + desloc_x[d], ny = y + desloc_y[d];
            if (nx < 1 || nx > linhas || ny < 1 || ny > colunas) continue;
            int novo_z = (z + grade[nx][ny]) % modulo_entrada;
            if (vis[nx][ny][novo_z]) continue;
            vis[nx][ny][novo_z] = 1;
            dist[nx][ny][novo_z] = dist[x][y][z] + 1;
            fila_bfs.push({nx, ny, novo_z});
        }
    }
    return (dist[linhas][colunas][0] != 0) ? dist[linhas][colunas][0] : -1;
}

int main() {
    cin >> linhas >> colunas >> modulo_entrada;
    if (modulo_entrada == 2) {
        cout << linhas + colunas - 2 << endl;
        return 0;
    }
    modulo_entrada--;
    for (int i = 1; i <= linhas; i++) {
        for (int j = 1; j <= colunas; j++) {
            cin >> grade[i][j];
            grade[i][j] %= modulo_entrada;
        }
    }
    int descarte;
    for (int i = 1; i <= linhas; i++) {
        for (int j = 1; j <= colunas; j++) {
            cin >> descarte;
        }
    }
    cout << bfs_solucao() << endl;
    return 0;
}