迷宮-広さ優先検索

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
#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;
    }
}

三、まとめ
広さ優先探索を用いて最適解を探す,すなわちここでは最短距離である.