A distância mínima entre o início e o final da passagem deve visitar pontos em um labirinto
Então, suponha que eu tenha um labirinto, que tenha um ponto de início e um ponto final, marcados com laranja e vermelho, respectivamente, e meu objetivo é encontrar a distância mínima entre eles. O caminho bloqueado é representado pela cor preta e o caminho aberto é representado pela cor branca. No entanto, existem duas modificações feitas nisso.
Existem algumas células que devem ser visitadas, marcadas na cor cinza.Qualquer célula pode ser visitada várias vezes (até o início, o término e deve visitar pontos)para ex- B = Preto, W = branco, G = cinza, R = Vermelho, O = laranja
BBBBBB BBBBB
BBGBBB BWGGB
MAZE1 => BOWGRB MAZE2 => BOBBB
BBGBBB BWWRB
BBBBBB BBBBB
Aqui, neste caso, ans será
MAZE1 => M[2][1] => [2][2] => [1][2] => [2][2] => [3][2] => [2][2] => [2][3] => [2][4] = 7
MAZE2 => M[1][1] => [1][2] => [2][2] => [3][2] => [3][3] => [3][2] => [2][2] = 6
Como você pode ver, os nós aparecem várias vezes
Primeiro, pensei em usar a técnica de recursão (backtracking), mas não consegui chegar a um algoritmo. e
Então eu pensei em usar dessa maneira.
Vou acompanhar todas as coordenadas dos pontos de visita obrigatória, pontos de partida e chegadaEncontre a distância entre cada nó (como no tipo de seleção, comparamos todos os termos, assim, obtemos a distância mínima entre cada nó (usando BFS))Em seguida, aplique algum algoritmo de distância mínima. Eu pensei em TSP, mas diz que os nós devem ser visitados exatamente uma vez. Aqui pode ser várias vezes. Eu encontrei o problema do carteiro chinês, mas não sei se ele pode ser aplicado aqui. O algoritmo de Floyd Warshall está lá, mas não inclui todos os pontosComo devo proceder, alguma ideia?