迷宮-広さ優先検索
2896 ワード
一、Problem description
君はどこにいるんだ?And you can only walk in four directions:up, down,left, right.
There will only be 5 kinds of characters in the maze.The meaning of each is as followed.
"#"is for rock, which you can not walk through.
"S"is for start.
"E"is for end.
"."is for road.
"!"マグマ
Input
n,m represent the maze is a nxm maze.(n rows, m columnsm,0
Then is the maze.
e.g.
5 5
#####
#S..#
#.!.#
#.#E#
#####
Output
You need to give the least steps to walk from start to the end.If it doesn't exist, then output -1.
e.g.(for the example in input)
4
二、My answer
三、まとめ
広さ優先探索を用いて最適解を探す,すなわちここでは最短距離である.
君はどこにいるんだ?And you can only walk in four directions:up, down,left, right.
There will only be 5 kinds of characters in the maze.The meaning of each is as followed.
"#"is for rock, which you can not walk through.
"S"is for start.
"E"is for end.
"."is for road.
"!"マグマ
Input
n,m represent the maze is a nxm maze.(n rows, m columnsm,0
Then is the maze.
e.g.
5 5
#####
#S..#
#.!.#
#.#E#
#####
Output
You need to give the least steps to walk from start to the end.If it doesn't exist, then output -1.
e.g.(for the example in input)
4
二、My answer
#include
#include
using namespace std;
struct point { //
int x;
int y;
point(int a = 0, int b = 0) {
x = a;
y = b;
}
void operator=(point a) {
x = a.x;
y = a.y;
}
};
int main() {
int n, m;
cin >> n >> m;
int d[n][m]; //
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) { // , -1
d[i][j] = -1;
}
}
char map[21][21];
queue q; //
point start(0, 0); //
point end(0, 0); //
int dx[4] = {1, 0, -1, 0}; // ,
int dy[4] = {0, 1, 0, -1}; // dxy[4][2] = {{1, 0},{0, 1},{-1, 0},{0, -1}}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> map[i][j];
if (map[i][j] == 'S') { //
start.x = i;
start.y = j;
} else if (map[i][j] == 'E') {
end.x = i; //
end.y = j;
}
}
}
q.push(start); //
point p;
d[start.x][start.y] = 0; //
while (!q.empty()) {
p = q.front();
q.pop();
if (p.x == end.x&&p.y == end.y) { //
break;
}
for (int i = 0; i < 4; i++) {
int nx = p.x + dx[i];
int ny = p.y + dy[i]; // ,
if (nx >= 0&&nx < n&&ny >= 0&&ny < m&&map[nx][ny] != '#'&&map[nx][ny] != '!'
&&d[nx][ny] == -1) { // ,
q.push(point(nx, ny)); // d[nx][xy] = -1
d[nx][ny] = d[p.x][p.y]+1; //
}
}
}
if (d[end.x][end.y] == -1) {
cout << "-1" << endl; //
} else {
cout << d[end.x][end.y] << endl;
}
}
三、まとめ
広さ優先探索を用いて最適解を探す,すなわちここでは最短距離である.