Это моя реализация с использованием простой BFS. Dijkstra также будет работать (вместо stl::priority_queue, который сортируется по убыванию стоимости для stl::queue), но будет серьезно излишним.
Здесь следует обратить внимание на то, что мы на самом деле ищем график, узлы которого не совсем соответствуют ячейкам в данном массиве. Чтобы добраться до этого графика, я использовал простую заливку на основе DFS (вы также можете использовать BFS, но DFS для меня немного короче). Для этого нужно найти все подключенные и одинаковые символьные компоненты и назначить их одному цвету / узлу. Таким образом, после заливки мы можем узнать, какому узлу принадлежит каждая ячейка в базовом графе, посмотрев на значение color [row] [col]. Затем я просто перебираю ячейки и нахожу все ячейки, в которых смежные ячейки не имеют одинаковый цвет (то есть находятся в разных узлах). Это, следовательно, ребра нашего графа. Я поддерживаю stl::set ребер, поскольку я перебираю ячейки, чтобы исключить дублирование ребер. После этого достаточно просто создать список смежности из списка ребер, и мы готовы к bfs.
Код (на С ++):
#include <queue>
#include <vector>
#include <iostream>
#include <string>
#include <set>
#include <cstring>
using namespace std;
#define SIZE 1001
vector<string> board;
int colour[SIZE][SIZE];
int dr[]={0,1,0,-1};
int dc[]={1,0,-1,0};
int min(int x,int y){ return (x<y)?x:y;}
int max(int x,int y){ return (x>y)?x:y;}
void dfs(int r, int c, int col, vector<string> &b){
if (colour[r][c]<0){
colour[r][c]=col;
for(int i=0;i<4;i++){
int nr=r+dr[i],nc=c+dc[i];
if (nr>=0 && nr<b.size() && nc>=0 && nc<b[0].size() && b[nr][nc]==b[r][c])
dfs(nr,nc,col,b);
}
}
}
int flood_fill(vector<string> &b){
memset(colour,-1,sizeof(colour));
int current_node=0;
for(int i=0;i<b.size();i++){
for(int j=0;j<b[0].size();j++){
if (colour[i][j]<0){
dfs(i,j,current_node,b);
current_node++;
}
}
}
return current_node;
}
vector<vector<int> > build_graph(vector<string> &b){
int total_nodes=flood_fill(b);
set<pair<int,int> > edge_list;
for(int r=0;r<b.size();r++){
for(int c=0;c<b[0].size();c++){
for(int i=0;i<4;i++){
int nr=r+dr[i],nc=c+dc[i];
if (nr>=0 && nr<b.size() && nc>=0 && nc<b[0].size() && colour[nr][nc]!=colour[r][c]){
int u=colour[r][c], v=colour[nr][nc];
if (u!=v) edge_list.insert(make_pair(min(u,v),max(u,v)));
}
}
}
}
vector<vector<int> > graph(total_nodes);
for(set<pair<int,int> >::iterator edge=edge_list.begin();edge!=edge_list.end();edge++){
int u=edge->first,v=edge->second;
graph[u].push_back(v);
graph[v].push_back(u);
}
return graph;
}
int bfs(vector<vector<int> > &G, int start, int end){
vector<int> cost(G.size(),-1);
queue<int> Q;
Q.push(start);
cost[start]=0;
while (!Q.empty()){
int node=Q.front();Q.pop();
vector<int> &adj=G[node];
for(int i=0;i<adj.size();i++){
if (cost[adj[i]]==-1){
cost[adj[i]]=cost[node]+1;
Q.push(adj[i]);
}
}
}
return cost[end];
}
int main(){
string line;
int rows,cols;
cin>>rows>>cols;
for(int r=0;r<rows;r++){
line="";
char ch;
for(int c=0;c<cols;c++){
cin>>ch;
line+=ch;
}
board.push_back(line);
}
vector<vector<int> > actual_graph=build_graph(board);
cout<<bfs(actual_graph,colour[0][0],colour[rows-1][cols-1])<<"\n";
}
Это просто быстрый взлом, можно внести множество улучшений. Но я думаю, что он довольно близок к оптимальному с точки зрения сложности времени выполнения и должен работать достаточно быстро для плат размером в несколько тысяч (не забудьте изменить #define из SIZE). Кроме того, я проверил это только в одном случае, который вы предоставили. Итак, как сказал Кнут, «Остерегайтесь ошибок в приведенном выше коде; я только доказал, что это правильно, а не пробовал». :.)