#include #include using namespace std; int H, W; int S_i, S_j, G_i, G_j; int total_paths = 0; // グリッドのサイズが最大 6x6 なので、ビットマスクで訪問状態を管理します // ただし、再帰の深さが最大で 36 になるので、スタックオーバーフローの心配はありません vector> visited; void dfs(int x, int y) { // ゴールに到達した場合、パスの数をインクリメント if (x == G_i && y == G_j) { total_paths++; return; } // 上下左右の移動 const int dx[4] = {0, 1, 0, -1}; const int dy[4] = {1, 0, -1, 0}; for (int dir = 0; dir < 4; ++dir) { int nx = x + dx[dir]; int ny = y + dy[dir]; // グリッドの範囲内か確認 if (nx >= 0 && nx < H && ny >= 0 && ny < W) { // 訪問していない場合 if (!visited[nx][ny]) { visited[nx][ny] = true; dfs(nx, ny); visited[nx][ny] = false; // バックトラック } } } } int main() { cin >> H >> W; cin >> S_i >> S_j; cin >> G_i >> G_j; // 0-index に調整 S_i--; S_j--; G_i--; G_j--; visited.assign(H, vector(W, false)); visited[S_i][S_j] = true; dfs(S_i, S_j); cout << total_paths << endl; return 0; }