e01

• Problem
  

• Code

#include <iostream>
#include <stack>
#include <vector>
#include <sstream>
#include <algorithm>
#include <functional>
using namespace std;
int row = 5, col = 5, length = col * row;

class Node {
public:
    Node(int x = 0, int y = 0) : x(x), y(y), index(x*5+y) {}
    int toIndex() {
        return index;
    }
    int isValid() {
        return 0 <= x && x < row && 0 <= y && y < col;
    }
    Node move(int x_dis, int y_dis) {
        return Node(x + x_dis, y + y_dis);
    }
    string toString() {
        string t;
        stringstream ss;
        ss << "(" << x << "," << y << ")";
        ss >> t;
        return t;
    }
private:
    int x;
    int y;
    int index;
};

void inputData(int *area) {
    for (int i = 0; i < length; i++) {
        cin >> area[i];
    }
}

void search(int *area, int length, vector<Node> &rs) {
    bool *moved = new bool [length];
    int direction[][2] = {
        {0, -1},
        {0, 1},
        {-1, 0},
        {1, 0}
    };
    stack<Node> path;
    Node next;

    function<bool(Node)> find = [&](Node cur) -> bool {
        moved[cur.toIndex()] = true;
        path.push(cur);

        if (cur.toIndex() == length - 1) {
            return true;
        }
        for (int i = 0; i < 4; i++) {
            next = cur.move(direction[i][0], direction[i][1]);
            if (next.isValid() && area[next.toIndex()] != 1 && !moved[next.toIndex()] && find(next)) {
                return true;
            }
        }
        path.pop();
        return false;
    };

    for (int i = 0; i < length; i++) {
        moved[i] = false;
    }

    rs.clear();
    find(Node(0, 0));
    if (path.size()) {
        while (!path.empty()) {
            rs.insert(rs.begin(), path.top());
            path.pop();
        }
    }

    delete[] moved;
}

void display(vector<Node> rs) {
    if (rs.size()) {
        for_each(rs.begin(), rs.end(), [](Node t)->void{ cout << t.toString() << endl; });
    }
    else {
        cout << "No Result" << endl;
    }

}

int main() {
    int area[25];
    vector<Node> rs;
    inputData(area);
    search(area, 25, rs);
    display(rs);
    return 0;
}

• Result