迷宫问题

image.png
image.png
image.png
image.png

几个知识点：

1. pair<int,int>用 make_pair(0,0)
2. dfs探索之后要记得还原
3. int** maze的设置
4. 一定要当心全局变量，在每一个运行中重置一下，minsize
   解法一：DFS

//
// Created by ljs on 2018/8/27.
//
#include <iostream>
#include <vector>
using namespace std;
vector<pair<int, int>> res;
int minsize = 200;
int m, n;
int dir[4][4] = {{-1, 0}, {0, 1},{1, 0}, {0, -1}};
void search(int x, int y, int m , int n, vector<pair<int, int>>& path, int** maze){
    if(x == m - 1 && y == n - 1 ){
        if(path.size() < minsize){
            res = path;
            minsize = res.size();
        }
        return;
    }
    else{
        for(int i = 0; i < 4; i++){
            int xx = x + dir[i][0];
            int yy = y + dir[i][1];
            if(xx < 0 || xx >= m || yy < 0 || yy >= n || maze[xx][yy] == 1)
                continue;
            maze[xx][yy] = 1;
            path.push_back(make_pair(xx,yy));//make_pair的使用
            search(xx, yy, m, n, path, maze);
            path.pop_back(); //一定要还原
            maze[xx][yy] = 0;//还原

        }
    }
}
int main(){


    while(cin>>m>>n){
        minsize = 200;//一定要重新更新
        int **maze = new int*[m];
        for(int i = 0; i < m; i++)
            maze[i] = new int[n];//学会此种定义方式
        for(int i = 0; i < m; i++){
            for(int j = 0 ; j < n; j++){
                cin>>maze[i][j];
            }
        }
        vector<pair<int, int>> path;
        path.push_back(make_pair(0,0));
        search(0, 0, m, n, path, maze);
        for(int i = 0 ; i < res.size(); i++){
            cout<<"("<<res[i].first<<","<<res[i].second<<")"<<endl;//对pair，用first和second
        }
    }
    return 0;
}

解法二：BFS
注意：全全局变量的默认初始化为0;
但是main中的初始化是随机数，所以要初始化！！！！
注意结构体的写法；

//
// Created by ljs on 2018/8/27.
//
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int m, n;
int dir[4][4] = {{-1, 0}, {0, 1},{1, 0}, {0, -1}};
struct node{
    int r;
    int c;
};
void print_path(node u, int d[10][10], node father[10][10]){
    vector<node> nodes;
    while(1){
        nodes.push_back(u);
        if(d[u.r][u.c] == 0)
            break;
        u = father[u.r][u.c];
    }
    for(int i = nodes.size() - 1; i >= 0 ;i-- ){
        cout<<"("<<nodes[i].r<<","<<nodes[i].c<<")"<<endl;
    }

}
void bfs(int visited[10][10], int maze[10][10], int d[10][10],node father[10][10]){
    queue<node> q;
    d[0][0] = 0;
    node zero;
    zero.r = 0;
    zero.c = 0;
    q.push(zero);
    visited[0][0] = 1;
    while(!q.empty()){
//        cout<<"qqq"<<endl;
        node cur = q.front();
        q.pop();
        int level = d[cur.r][cur.c];
//        cout<<cur.r<<cur.c<<endl;
        if(cur.r == m - 1 && cur.c == n-1){
            print_path(cur,d,father);
            return;
        }
        else{
            for(int i = 0; i < 4; i++){
                int xx = cur.r + dir[i][0];
                int yy = cur.c + dir[i][1];
                if(xx > m-1 || xx < 0 || yy > n-1 || yy < 0 || visited[xx][yy] == 1 || maze[xx][yy] ==  1){

//                    cout<<"continue"<<endl;
                    continue;
                }
                node tmp;
                tmp.r = xx;
                tmp.c = yy;
                q.push(tmp);
                //cout<<"push"<<endl;
                visited[xx][yy] = 1;
                father[xx][yy] = cur;
                d[xx][yy] = level + 1;
            }
        }
    }
}
int main(){
    while(cin>>m>>n){
        int maze[10][10];
//        cout<<"hhhh"<<endl;
        queue<node> q;
        for(int i = 0; i < m; i++){
            for(int j = 0 ; j < n; j++){
                cin>>maze[i][j];
            }
        }
        node father[10][10];
        int visted[10][10];
        for(int i = 0; i < 10; i++){
            for(int j = 0 ; j < 10; j++){
                visted[i][j] = 0;
            }
        }
        vector<node> nodes;
        int d[10][10];
//        cout<<"kkkkkkk"<<endl;
        bfs(visted, maze, d, father);

    }
    return 0;
}