#include #include #include #include #include #include using namespace std; struct POS : public complex { POS(int x, int y) : complex(x, y){} POS(const complex& c) : complex(c){} bool operator<(const POS& rh)const{ if (real() == rh.real()){ return imag() < rh.imag(); } return real() < rh.real(); } }; const POS DIR[] = { POS(0, -1),POS(0, 1),POS(1, 0),POS(-1, 0) }; int TABLE[8][8]; int W, H; vector > > graph; map node_map; bool IsIn(const POS& p) { return 0 <= p.real() && p.real() <= W && 0 <= p.imag() && p.imag() <= H; } void BFS(int node, const POS& start) { set open; open.insert(start); int close[8][8]; memset(close, 0, sizeof(close)); close[start.real()][start.imag()] = 1; for (int i = 0; i < 5; ++i){ set open2; for (set::iterator it = open.begin(); it != open.end(); ++it){ const POS& now = *it; for (int dir = 0; dir < 4; ++dir){ const POS next = now + DIR[dir]; if (!IsIn(next) || close[next.real()][next.imag()]){ continue; } close[next.real()][next.imag()] = 1; if (TABLE[next.real()][next.imag()] != 0){ open2.insert(next); if (TABLE[next.real()][next.imag()] != 1){ graph[node].push_back(make_pair(node_map[next], i + 1)); } } } } swap(open, open2); } } int D(int start, int goal) { vector cache(node_map.size(), INT_MAX); map open; open.insert(make_pair(0, start)); cache[start] = 0; while (!open.empty()){ int time = open.begin()->first; int pos = open.begin()->second; open.erase(open.begin()); for (vector >::iterator it = graph[pos].begin(); it != graph[pos].end(); ++it){ int next = it->first; int cost = it->second; if (cache[next] > time + cost){ cache[next] = time + cost; open.insert(make_pair(time + cost, next)); } } } if (cache[goal] == INT_MAX){ return -1; } return cache[goal]; } main() { while (cin >> W >> H && W){ graph.clear(); graph.resize(64); node_map.clear(); int ant = -1; int hole = -1; for (int y = 0; y < H; ++y){ for (int x = 0; x < W; ++x){ int in; cin >> in; TABLE[x][y] = in; if (in >= 2){ int id = (int)node_map.size(); if (in == 2){ //ant ant = id; } else if (in == 3){ hole = id; } node_map.insert(make_pair(POS(x, y), id)); } } } for (map::iterator it = node_map.begin(); it != node_map.end(); ++it){ BFS(it->second, it->first); } cout << D(ant, hole) << endl; } }