#include <iostream>
#include <string>
#include <vector>
#include <unordered_set>
#include <unordered_map>
#include <array>
using namespace std;
size_t hashSeed = 0;
size_t rotl(const size_t value, const int shift) {
if ((shift &= sizeof(value)*8 - 1) == 0)
return value;
return (value << shift) | (value >> (sizeof(value) * 8 - shift));
}
struct Vec2 {
int x, y;
Vec2() : x(0), y(0) {}
Vec2(int x, int y) : x(x), y(y) {}
// 一种很evil的写法，把vector作为索引，而不是把vector作为索引
int& operator[](vector<vector<int>>& arr) const {
return arr[y][x];
}
char& operator[](vector<string>& arr) const {
return arr[y][x];
}
bool operator==(const Vec2& other) const {
return x == other.x && y == other.y;
}
bool operator!=(const Vec2& other) const {
return x != other.x || y != other.y;
}
Vec2 operator+(const Vec2& other) const {
return { x + other.x, y + other.y };
}
};
template<>
class std::hash<Vec2> {
public:
size_t operator()(const Vec2& p) const {
const size_t Prime3 = 3266489917U;
const size_t Prime4 = 668265263U;
size_t hash = hashSeed;
hash = rotl(hash + (size_t)p.x * Prime3, 17) * Prime4;
hash = rotl(hash + (size_t)p.y * Prime3, 17) * Prime4;
return hash;
}
};
int main() {
hashSeed = time(NULL) + 374761393U;
int k, w, h;
Vec2 atori, natsuki;
cin >> k >> w >> h;
cin >> atori.x >> atori.y >> natsuki.x >> natsuki.y;
cin.ignore();
auto mp = vector<string>(h, string(w, '.'));
for (auto i = 0; i < h; i++) {
getline(cin, mp[i]);
}
array<array<Vec2, 2>, 10> portals;
for (auto& p : portals) {
p[0] = p[1] = Vec2(-1, -1);
}
for (auto pos = Vec2(0, 0); pos.y < h; pos.y++) {
for (pos.x = 0; pos.x < w; pos.x++) {
if (!isdigit(pos[mp]))
continue;
auto idx = pos[mp] - '0';
(portals[idx][0].x == -1 ? portals[idx][0] : portals[idx][1]) = pos;
}
}
int step = -1;
auto directions = vector<Vec2>{ {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
auto visited = vector<vector<int>>(h, vector<int>(w, -1));
auto nowVisit = unordered_set<Vec2>();
auto nextVisit = unordered_set<Vec2>{ atori };
auto postUpdate = unordered_map<Vec2, int>();
atori[visited] = k;
while (!nextVisit.empty()) {
step++;
nextVisit.swap(nowVisit);
nextVisit.clear();
postUpdate.clear();
for (const auto& pos : nowVisit) {
if (pos == natsuki) {
cout << step << endl;
return 0;
}
auto nextK = pos[visited] - 1;
if (nextK < 0) {
continue;
}
for (auto& dir : directions) {
auto nextPos = pos + dir;
if (nextPos.x < 0 || nextPos.x >= w || nextPos.y < 0 || nextPos.y >= h) {
continue;
}
if (nextPos[visited] >= nextK) {
continue;
}
auto type = nextPos[mp];
if (type == '#') {
continue;
}
else if (type == 'S') {
postUpdate[nextPos] = k;
}
else if (isdigit(type)) {
auto idx = type - '0';
auto& portal = portals[idx];
auto tpPos = portal[0] == nextPos ? portal[1] : portal[0];
if (tpPos[visited] < nextK) {
tpPos[visited] = nextK;
nextVisit.insert(tpPos);
}
}
postUpdate[nextPos] = max(postUpdate[nextPos], nextK);
nextVisit.insert(nextPos);
}
}
for (auto& [pos, newK] : postUpdate) {
pos[visited] = newK;
}
}
cout << "BE" << endl;
return 0;
}
