题解 P1238 【走迷宫】

jhdonghj · 2019-05-01 16:38:33 · 题解

基本思路：dfs

这题感觉就基本上裸dfs修改一下限制条件之后再写个输出函数和路径数组就好了

感觉我的代码可读性还不错，过来分享一波

#include<bits/stdc++.h>
using namespace std;

struct point    //结构体存储点信息
{
    int x, y;
}st, ed;
int m, n, mp[15][15], vis[15][15];      //mp为地图,vis为访问标记
int sd[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };       //注意前后顺序，左上右下
bool cango = false;     //有解标记
vector<point> step;     //路径数组

bool operator==(point a, point b) {     //为了代码可读性用重载运算符
    return a.x == b.x && a.y == b.y;
}

void print() {
    cout << '(' << step[0].x << ',' << step[0].y << ')';
    for (int i = 1; i < step.size(); i++) {
        cout << "->(" << step[i].x << ',' << step[i].y << ')';
    }
    cout << endl;
    return;
}

bool check(point a) {       //判断传入点能否走通
    return 1 <= a.x && a.x <= m && 1 <= a.y && a.y <= n &&
        !vis[a.x][a.y] && mp[a.x][a.y];
}

void dfs(point a) {
    if (a == ed) {
        cango = true;   //标记有解
        print();        //输出
        return;
    }
    point tmp;
    for (int i = 0; i < 4; i++) {
        tmp.x = a.x + sd[i][0], tmp.y = a.y + sd[i][1];
        if (check(tmp)) {
            //执行下一次搜索，并标记相关数据
            step.push_back(tmp);
            vis[tmp.x][tmp.y] = 1;
            dfs(tmp);
            vis[tmp.x][tmp.y] = 0;
            step.pop_back();
        }
    }
    return;
}

int main() {
    //输入
    cin >> m >> n;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            cin >> mp[i][j];
    cin >> st.x >> st.y >> ed.x >> ed.y;
    //dfs开始
    vis[st.x][st.y] = 1;
    step.push_back(st);
    dfs(st);
    //判断是否有解,无解输出-1
    if (!cango)
        cout << -1 << endl;
    return 0;
}