题解 | #迷宫问题#

/*
代价：pair(F, G)
使用map进行记录

坐标前进关系
通过map记录
*/

/*
流程
openlist // 记录当前可访问的位置
//从可访问位置筛选F值最高坐标，判断是否是目标坐标，将其从openlist中移走，放入closelist
//访问该坐标所有可探寻路径，1. 不可探寻或在closelist，则跳过 2.未曾访问过，加入openlist, 代价列表更新代价,记录坐标前进关系
//删除访问坐标代价记录
*/

#include <iostream>
#include <map>
#include <vector>
#include <string>
#include <set>
using namespace std;

typedef pair<int, int> pos;
typedef vector<vector<int>> plat_t;
class Maze {
  public:
    Maze(const plat_t &plat, const pos& start,
         const pos& target): m_plat(plat), m_start_pos(start), m_target_pos(target),
        m_x_move_choices{-1, 0, 1}, m_y_move_choices{-1, 0, 1} {
        m_cost_record[start] = {0,0};
    }

    int get_plat_info(pos current_pos) {
        return m_plat[current_pos.first][current_pos.second];
    }

    int path_plan() {
        if (!check_plat_valid()) {
            return -1;
        }

        while (m_cost_record.size()) {
            auto iter = m_cost_record.begin();
            pos current_pos = iter->first;
            if(current_pos.first == m_target_pos.first && current_pos.second == m_target_pos.second){
                return 0;
            }
            cost current_cost = iter->second;
            m_cost_record.erase(iter);
            m_closelist.insert(current_pos);

            for (int x_offset : m_x_move_choices) {
                for (int y_offset : m_y_move_choices) {
                    if ((!x_offset || !y_offset) && (x_offset || y_offset)) {
                        pos next_pos = make_pair(current_pos.first + x_offset,
                                                 current_pos.second + y_offset);
                        if (!check_pos_valid(next_pos) || get_plat_info(next_pos) == 1 || m_closelist.count(next_pos)) {
                            continue;
                        }

                        int tmp_g = current_cost.g_weight + 1;
                        int tmp_f = tmp_g + 1;
                        cost tmp = {tmp_f, tmp_g};
                        if (!m_cost_record.count(next_pos)) {
                            m_cost_record[next_pos] = tmp;
                            m_move_record[next_pos] = current_pos;
                        } else {
                            if (m_cost_record[next_pos].f_weight > tmp_f) {
                                m_cost_record[next_pos] = tmp;
                                m_move_record[next_pos] = current_pos;
                            }
                        }

                    }
                }
            }
        }

        return -1;
    }

    int get_path(){
        int ret = path_plan();
        if(ret){
            cout << "no result, plat is invalid!!!\n";
            return ret;
        }

        vector<pos> result{m_target_pos};
        while(m_move_record.count(result.back())){
            result.push_back(m_move_record[result.back()]);
        }
        for(auto iter=result.rbegin(); iter != result.rend(); iter++){
            printf("(%d,%d)\n",iter->first,iter->second);
        }
        return 0;
    }


  private:
    plat_t m_plat;
    pos m_start_pos;
    pos m_target_pos;

    const vector<int> m_x_move_choices;
    const vector<int> m_y_move_choices;

    int m_row_limit;
    int m_column_limit;

    bool check_plat_valid() {
         m_row_limit = m_plat.size();
        if (m_row_limit == 0) {
            return 0;
        }

         m_column_limit = m_plat[0].size();
        for (int i = 1; i < m_plat.size(); i++) {
            if (m_column_limit != m_plat[i].size()) {
                return 0;
            }
        }
        return 1;
    }

    bool check_pos_valid(pos current_pos) {
        if (current_pos.first < 0 || current_pos.second < 0) {
            return 0;
        }
        if (current_pos.first >= m_row_limit || current_pos.second >= m_column_limit) {
            return 0;
        }
        return 1;
    }


    typedef struct cost_t {
        int f_weight;
        int g_weight;
    } cost;
    map<pos, cost> m_cost_record;
    set<pos> m_closelist;
    map<pos, pos> m_move_record;
};

int main() {
    int row, column;
    cin >> row >> column;

    plat_t plat(row,vector<int>(column));
    for(int i = 0; i < row; i++){
        for( int j=0; j< column;j++){
            int tmp; cin >> tmp;
            plat[i][j] = tmp;
        }
    }

    pos start = {0,0};
    pos end = {row-1, column-1};
    Maze maze(plat,start, end);
    maze.get_path();

}
// 64 位输出请用 printf("%lld")