#include #include #include #include #include #include #include #include #include #include #include #include #include #define rep(i, n) for(i = 0; i < n; i++) #define int long long using namespace std; int dy[4] = {-1, 0, 1, 0}; int dx[4] = {0, 1, 0, -1}; int h, w, sy, sx, gy, gx; void dfs(int y, int x, vector &used, vector &path, vector> &paths) { path.push_back(y * w + x); used[y * w + x] = true; bool ng = false; for (int i = 0; i < h - 1; i++) { for (int j = 0; j < w - 1; j++) { if (used[i * w + j] && used[i * w + j + 1] && used[(i + 1) * w + j] && used[(i + 1) * w + j + 1]) { ng = true; break; } } if (ng) break; } if (ng) { used[y * w + x] = false; path.pop_back(); return; } if (y == gy && x == gx) { paths.push_back(path); used[y * w + x] = false; path.pop_back(); return; } for (int i = 0; i < 4; i++) { int ny = y + dy[i]; int nx = x + dx[i]; if (ny < 0 || ny >= h || nx < 0 || nx >= w || used[ny * w + nx]) continue; dfs(ny, nx, used, path, paths); } path.pop_back(); used[y * w + x] = false; } bool check(vector path) { const int INF = 114514; int i; vector> wall(h, vector(w, true)); vector> dist(h, vector(w, INF)); rep(i, path.size()) { wall[path[i] / w][path[i] % w] = false; } typedef pair P; queue

que; que.push(P(sy, sx)); dist[sy][sx] = 0; while (!que.empty()) { P now = que.front(); que.pop(); int y = now.first; int x = now.second; rep(i, 4) { int ny = y + dy[i]; int nx = x + dx[i]; if (ny < 0 || ny >= h || nx < 0 || nx >= w || wall[ny][nx] || dist[ny][nx] <= dist[y][x] + 1) continue; dist[ny][nx] = dist[y][x] + 1; que.push(P(ny, nx)); } } /*cout << "path: "; rep(i, path.size()) cout << path[i] << " "; cout << endl; rep(i, h) { for (int j = 0; j < w; j++) { if (dist[i][j] >= INF) cout << "x "; else cout << dist[i][j] << " "; } cout << endl; }*/ return dist[gy][gx] == path.size() - 1; } signed main() { cin >> h >> w >> sy >> sx >> gy >> gx; sy--; sx--; gy--; gx--; vector path; vector> paths; vector used(h * w); dfs(sy, sx, used, path, paths); int ans = 0; for (vector path: paths) { if (check(path)) ans++; } cout << ans << endl; return 0; }