#include "helpers.cpp"

#include<cstdio>
#include<iostream>
#include<vector>
#include<set>
#include<queue>
#include<fstream>

#include <boost/config.hpp>
#include <boost/bimap.hpp>
#include <boost/graph/strong_components.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/graph/adj_list_serialize.hpp> 
#include <boost/archive/text_oarchive.hpp>
#include <boost/serialization/map.hpp>
#include <boost/serialization/set.hpp>
#include <boost/unordered_set.hpp>

using namespace std;

typedef pair<int, int> pii;
typedef pair< pii, set< pii > > state;

typedef boost::adjacency_list<boost::listS, boost::vecS, boost::directedS, Vertex, Edge> Graph;
typedef boost::graph_traits<Graph>::vertex_descriptor vertex_t;
typedef boost::graph_traits<Graph>::edge_descriptor edge_t;

typedef boost::bimap< state, vertex_t > StateMap;
typedef StateMap::value_type mapping;

int width, height, boxes_cnt, man_row, man_col;
vector< vector<bool> > isWall;
set< pii > boxes, targets;

Graph state_graph;
boost::unordered_map<pii, boost::unordered_map<pii, int>> box_distance;

boost::unordered_map<set<pii>, int> memo_h;

void read() {
    if (scanf("%d %d", &width, &height) != 2) exit(1);
    isWall.resize(height, vector<bool>(width));
    for (int r = 0; r<height; ++r) {
        for (int c = 0; c<width; ++c) {
            int wall;
            if (scanf("%d", &wall) != 1) exit(1);
            isWall[r][c] = wall == 1;
        }
    }

    if (scanf("%d", &boxes_cnt) != 1) exit(1);
    for (int i = 0; i<boxes_cnt; ++i) {
        int r,c;
        if (scanf("%d %d", &r, &c) != 2) exit(1);
        boxes.insert({r, c});
    }
    for (int i = 0; i<boxes_cnt; ++i) {
        int r,c;
        if( scanf("%d %d", &r, &c) != 2) exit(1);
        targets.insert({r, c});
    }

    if (scanf("%d %d", &man_row, &man_col) != 2) exit(1);
}

// Compute the shortesth path from each target to all tiles.
void box_bfs() {
    int dr[4] = {0,1,0,-1};
    int dc[4] = {1,0,-1,0};

    for (const pii& target : targets) {
        queue< pii > q;
        q.push(target);

        boost::unordered_map<pii, int> dis;
        dis[target] = 0;

        while (!q.empty()) {
            pii where = q.front();
            q.pop();

            for (int i = 0; i<4; ++i) {
                int new_r = where.first + dr[i];
                int new_c = where.second + dc[i];
                pii next = {new_r, new_c};
                if (isWall[new_r][new_c]) continue;
                if (dis.find(next) == dis.end()) {
                    q.push(next);
                    dis[next] = dis[where] + 1;
                }
            }
        }

        box_distance[target] = dis;
    }
}

pair<state, bool> move(pii man, const set< pii> &boxes, int dr, int dc) {
    int nr = man.first + dr;
    int nc = man.second + dc;
    // Cannot walk through walls.
    if (isWall[nr][nc]) {
        return {{man, boxes}, false};
    }
    // Doesn't push any boxes.
    if (boxes.find({nr, nc}) == boxes.end()) {
        return {{{nr, nc}, boxes}, false};
    }
    int nbr = nr + dr;
    int nbc = nc + dc;
    // Trying to push two boxes at once.
    if (boxes.find({nbr, nbc}) != boxes.end()) {
        return {{man, boxes}, false};
    }
    // If pushing box to the wall.
    if (isWall[nbr][nbc]) {
        return {{man, boxes}, false};
    }
    set< pii > new_boxes(boxes);
    new_boxes.erase({nr, nc});
    new_boxes.insert({nbr, nbc});
    return {{{nr, nc}, new_boxes}, true};
}

int compute_min_pushes(const state& st) {
    const set<pii>& boxes = st.second;
    int sum_pushes = 0;
    for (const pii& box : boxes) {
        int min_pushes = -1;
        for (const pii& target : targets) {
            int d = box_distance[target][box];
            if (min_pushes == -1 || min_pushes > d) min_pushes = d;
        }
        sum_pushes += max(min_pushes, 0);
    }
    return sum_pushes;
}

int compute_h(const state& st) {
    auto it = memo_h.find(st.second);
    if (it != memo_h.end()) {
        return it->second;
    }
    vector<pii> boxes(st.second.begin(), st.second.end());
    vector<pii> v_targets(targets.begin(), targets.end());
    int min_h = -1;
    do {
        int sum_h = 0;
        for (unsigned i = 0; i<boxes.size(); ++i) {
            pii box = boxes[i];
            pii target = v_targets[i];
            int dis = box_distance[target][box];
            sum_h += dis;
        }
        if (min_h == -1 || min_h > sum_h) min_h = sum_h;
    } while (next_permutation(boxes.begin(), boxes.end()));
    memo_h[st.second] = min_h;
    return min_h;
}

void create_graph(string filename, string map_filename) {
    int dr[4] = {0,1,0,-1};
    int dc[4] = {1,0,-1,0};

    StateMap map_to_boost;

    queue< state > q;
    state start_state = {{man_row, man_col}, boxes};

    int cnt_nodes = 0;

    q.push(start_state);
    vertex_t u = boost::add_vertex(state_graph);
    map_to_boost.insert( mapping(start_state, u) );
    state_graph[u].id = cnt_nodes; cnt_nodes++;
    state_graph[u].starting = true;
    state_graph[u].winning = false;
    state_graph[u].h = compute_h(start_state);
    state_graph[u].min_pushes = compute_min_pushes(start_state);

    while (!q.empty()) {
        state where_st = q.front();
        q.pop();

        pii man;
        set< pii > boxes;
        tie(man, boxes) = where_st;

        vertex_t where = map_to_boost.left.find(where_st)->second;
        for (int i = 0; i<4; ++i) {
            pii new_man;
            set< pii > new_boxes;
            state next_state;
            bool moved_boxes;
            tie(next_state, moved_boxes) = move(man, boxes, dr[i], dc[i]);
            tie(new_man, new_boxes) = next_state;

            vertex_t next;
            if (map_to_boost.left.find(next_state) == map_to_boost.left.end()) {
                vertex_t u = boost::add_vertex(state_graph);
                map_to_boost.insert( mapping(next_state, u) );
                state_graph[u].id = cnt_nodes; cnt_nodes++;
                state_graph[u].starting = false;
                state_graph[u].winning = false;
                state_graph[u].h = compute_h(next_state);
                state_graph[u].min_pushes = compute_min_pushes(next_state);
                next = u;
                if (new_boxes != targets) {
                    q.push(next_state);
                } else {
                    state_graph[u].winning = true;
                }
            } else {
                next = map_to_boost.left.find(next_state)->second;
            }
            if (where != next) {
                edge_t edge; bool ok;
                tie(edge, ok) = boost::add_edge(where, next, state_graph);
                state_graph[edge].pushed = moved_boxes;
            }
        }
    }

    {
        std::ofstream dot_file(filename);
        boost::archive::text_oarchive oa(dot_file);
        oa << state_graph;
    }

    {
        std::ofstream dot_file(map_filename);
        boost::archive::text_oarchive oa(dot_file);
        oa << map_to_boost;
    }
}

int main(int argc, char* argv[]) {
    read();

    box_bfs();

    if (argc > 2) {
        create_graph(argv[1], argv[2]);
    }

    return 0;
}
