Solução de Frederico Bulhões
Para resolver esse problema podemos fazer uma BFS no grafo, guardando uma matriz a distância da fonte até a posição atual. Vamos dizer que caso uma posição tenha uma mina seu peso serpa 1, caso contrário 0. Quando vamos processar uma nova posição, passamos por todos os vértices adjacentes: caso o vértice que estamos tentando chegar ainda não tenha sido processado, dizemos que o peso dele seria o peso até a posição atual mais o peso do lugar que tentamos ir. Caso a posição que estamos indo não tenha mina colocamos a próxima posição no início da fila, caso tenha, no final.
Assim chegamos na posição final, e assim termos computado qual a quantidade mínima de minas que devemos passar para chegar lá.
Porém essa solução fica para o leitor.
É possível tambem fazer de outra forma, usando algoritmo de Dijkstra, como mostra o leitor Mateus Gonçalves.
Solução de Mateus Gonçalves
Este problema pode resolvido com uma implementação do algoritmo de Dijkstra para achar o menor caminho entre uma fonte fixa (que no caso é o elemento do canto superior esquerdo da matriz, de coordenadas {0, 0}) e os demais vértices. Não é preciso construir o grafo explicitamente, no entanto, já que sabemos que dado um elemento da matriz, os vértices adjacentes à ele são os elementos à esquerda, à direita, em cima e em baixo (se estes estiverem contidos na matriz). Portanto, basta definirmos um vetor de direções para iterar pela lista de adjacências implícita do grafo. Além disso, o elemento da matriz na linha i e coluna j irá denotar o “peso” das arestas que saem do mesmo (e entram também, pois o grafo não é dirigido).
Segue o código para melhor entendimento:
https://github.com/mateus-buarque6/Noic_solucoes/blob/master/mina.cpp