Dies ist meine Implementierung unter Verwendung eines einfachen BFS. Ein Dijkstra würde auch funktionieren (ersetzen Sie ein stl::priority_queue die nach absteigenden Kosten für die stl::queue ), aber das wäre wirklich zu viel des Guten.
Dabei ist zu beachten, dass wir eigentlich in einem Graphen suchen, dessen Knoten nicht genau den Zellen in der gegebenen Matrix entsprechen. Um zu diesem Graphen zu gelangen, habe ich ein einfaches DFS-basiertes Floodfill verwendet (man könnte auch BFS verwenden, aber DFS ist für mich etwas kürzer). Dabei werden alle zusammenhängenden Komponenten mit gleichem Zeichen gefunden und der gleichen Farbe/Knoten zugeordnet. So können wir nach dem Floodfill herausfinden, zu welchem Knoten jede Zelle im zugrundeliegenden Graphen gehört, indem wir uns den Wert von colour[row][col] ansehen. Dann iteriere ich einfach über die Zellen und finde alle Zellen heraus, bei denen benachbarte Zellen nicht die gleiche Farbe haben (d. h. zu verschiedenen Knoten gehören). Dies sind also die Kanten unseres Graphen. Ich pflege eine stl::set von Kanten, wenn ich über die Zellen iteriere, um doppelte Kanten zu eliminieren. Danach ist es eine einfache Angelegenheit, eine Adjazenzliste aus der Liste der Kanten zu erstellen und wir sind bereit für ein bfs.
Code (in C++):
#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";
}
Dies ist nur ein schneller Hack, es können noch viele Verbesserungen vorgenommen werden. Aber ich denke, es ist ziemlich nahe am Optimum, was die Laufzeitkomplexität angeht, und sollte schnell genug für Boards mit einer Größe von mehreren Tausend laufen (vergessen Sie nicht, die #define von SIZE ). Außerdem habe ich es nur mit dem einen Fall getestet, den Sie angegeben haben. Also, wie Knuth sagte: "Hüten Sie sich vor Fehlern im obigen Code; ich habe ihn nur als korrekt bewiesen, nicht ausprobiert." :).
