取得した最終グリッドで深さ優先検索 (dfs) を実行します。
http://en.wikipedia.org/wiki/Depth-first_search
個々のパスを取得します。最短のものを選択したい場合、実行できる最適化はほとんどありません。
- dfs がそれよりも先に見える場合は、そのパスをスキップします。
- 最大制限よりも短い長さのパスが見つかった場合。max-limit をそれに設定します。
これが役立つことを願っています。
編集:私はこのコードを書きました。それはあなたのために働くはずです。x、y座標としてのベクトル<ペア>で、最短パスを提供します。
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
ifstream fin("map.txt");
int width, height;
int map[10][10];
// Start (x,y), End (x,y)
int sy, sx, ey, ex;
bool visited[10][10];
vector<pair<int, int> > final_path;
int max_size = 9999;
void getInput() {
fin >> width >> height;
for (int i = 0; i < height; i++) {
for (int j = 0; j < width; j++) {
int x;
fin >> x;
map[i][j] = x;
if(x == 8){
sy = i;
sx = j;
}
if(x == 9){
ey = i;
ex = j;
}
}
}
}
void dfs(int x, int y, vector<pair<int, int> > path) {
if(path.size() > max_size){
cout << "Returning : path size too big" << endl;
return;
}
if(x < 0 || x >= width || y < 0 || y >= height){
cout << "Returning : bounds" << endl;
return;
}
// If the tile is blocked, can't go there
if(map[y][x] == 0){
cout << "Returning : blocked" << endl;
return;
}
if(visited[y][x]){
cout << "Returning : visited" << endl;
return;
}
// We don't want to revisit a tile
visited[y][x] = true;
cout << "Visiting " << x << " " << y << endl;
path.push_back(make_pair(x, y));
if(map[y][x] == 9) {
final_path = path;
visited[y][x] = false;
return;
}
dfs(x, y - 1, path);
dfs(x + 1, y, path);
dfs(x, y + 1, path);
dfs(x - 1, y, path);
visited[y][x] = false;
return;
}
int main() {
getInput();
cout << "Got Input" << endl;
cout << width << " " << height << endl;
memset(visited, 0, sizeof(visited));
vector<pair<int, int> > starting_path;
cout << sx << " " << sy << endl;
dfs(sx, sy, starting_path);
cout << "Path size is " << final_path.size() << endl;
for(int i = 0; i < final_path.size(); i++){
cout << final_path[i].first << " " << final_path[i].second << endl;
}
return 0;
}
map.txt には、質問で指定したマップが含まれています。
