Skip to content
TheChatArchiveThe Chat Archive
o1-mini-2024-09-12· OpenAIAi2 WildChat-4.8M (AI2)

MAZE 2022 (Tên file MAZE2022.cpp) An đã tạo ra một trò chơi mê cung. Trò chơi yêu cầu…

  1. User

    MAZE 2022 (Tên file MAZE2022.cpp) An đã tạo ra một trò chơi mê cung. Trò chơi yêu cầu điều khiển một nhân vật Bờm đi lấy chìa khóa để thoát khỏi mê cung trong thời gian ngắn nhất. Màn hình trò chơi được biểu diễn dưới dạng lưới các ô vuông gồm N dòng N cột. Mỗi ô tương ứng một trong các kí hiệu sau:  Dấu ‘#’ tương ứng với các ô có chướng ngại vật, Bờm không thể đi vào.  Dấu ‘.’ tương ứng với ô trống, Bờm có thể đi vào. Có 3 lệnh điều khiển Bờm: đi thẳng (Forward), xoay trái 90 độ ngược chiều kim đồng hồ (Left), xoay phải 90 độ cùng chiều kim đồng hồ (Right).  Lệnh Forward: Bờm đi thẳng đến ô kề phía trước mặt Bờm nếu ô này không có chướng ngại vật hoặc không phải ô ngoài đường biên, nếu không thỏa thì Bờm sẽ bỏ qua lệnh này và thực hiện lệnh kế tiếp.  Lệnh Left: Bờm sẽ đứng tại ô hiện tại và xoay trái 90 độ ngược chiều kim đồng hồ.  Lệnh Right: Bờm sẽ đứng tại ô hiện tại và xoay phải 90 độ ngược chiều kim đồng hồ. Yêu cầu: Biết rằng ban đầu Bờm đứng tại ô (N,1) dòng N cột 1 và Bờm hướng lên trên hoặc hướng qua phải, nhiệm vụ trò chơi là đưa ra một dãy lệnh điều khiển ngắn nhất để Bờm đến được ô mục tiêu (1,N) dòng 1, cột N. Dữ liệu: Cho trong file văn bản MAZE2022.INP: • Dòng đầu tiên gồm nguyên N (2 ≤ N ≤ 100, 1≤C≤2 ) số dòng, số cột màn hình trò chơi. • N dòng tiếp theo, mỗi dòng gồm một chuỗi N kí tự liên tiếp biểu diễn mê cung. Kết quả: Cho trong file văn bản MAZE2022.OUT số nguyên duy nhất cho biết thời gian di chuyển ngắn nhất Bờm luôn đến ô mục tiêu, mà không phụ thuộc vào hướng ban đầu của Bờm (lên trên hoặc sang phải). Ví dụ: MAZE2022.INP MAZE2022.OUT GIẢI THÍCH 3 .#. ... ... 9 Bờm xuất phát tại ô (3,1) và di chuyển đến ô (1,3). Dãy lệnh ngắn nhất như sau: Forward, Right, Forward, Forward, Left, Forward, Left, Forward, Forward

  2. Assistant

    To solve the MAZE 2022 problem, we need to determine the shortest sequence of commands that allows the character Bờm to navigate from the starting position (N, 1) to the target position (1, N) in an N x N grid maze. The sequence must work regardless of Bờm's initial facing direction, which can be either upwards or to the right.

    Problem Breakdown

    1. Grid Representation: The maze is represented as an N x N grid where:

      • '#' denotes an obstacle.
      • '.' denotes an empty space.
    2. Initial Conditions:

      • Starting Position: (N, 1)
      • Initial Directions: Up (0) or Right (1)
    3. Commands:

      • Forward: Move one cell in the current facing direction if possible.
      • Left: Rotate 90 degrees counter-clockwise.
      • Right: Rotate 90 degrees clockwise.
    4. Objective: Find the minimal number of commands that ensures Bờm reaches (1, N) regardless of whether he starts facing up or right.

    Solution Approach

    To solve this problem efficiently, we'll use Breadth-First Search (BFS), which explores all possible sequences of commands step by step until a valid solution is found. However, since Bờm can start facing either up or right, our BFS state must account for both scenarios simultaneously.

    Here's the step-by-step approach:

    1. State Representation:

      • For BFS, each state will represent Bờm's position and direction for both possible initial directions.
      • A state is represented as (x1, y1, dir1, x2, y2, dir2), where:
        • (x1, y1, dir1): Position and direction when starting facing up.
        • (x2, y2, dir2): Position and direction when starting facing right.
    2. Visited States:

      • To avoid revisiting the same state, we'll maintain a visited array or hash set that keeps track of already explored states.
    3. BFS Implementation:

      • Initialize the BFS queue with the starting state for both initial directions.
      • At each step, apply each possible command (Forward, Left, Right) and enqueue the resulting state if it's valid and hasn't been visited before.
      • Continue until both initial directions reach the target (1, N).
    4. Optimization:

      • Given that N can be up to 100, we need to optimize memory usage, especially for the visited states.
      • We'll encode the state into a unique identifier using bit manipulation to efficiently store and check visited states.

    C++ Implementation

    Below is the C++ code that implements the above approach:

    #include <bits/stdc++.h>
    using namespace std;
    
    // Directions: 0 = Up, 1 = Right, 2 = Down, 3 = Left
    int dx[4] = { -1, 0, 1, 0 };
    int dy[4] = { 0, 1, 0, -1 };
    
    struct State {
        int x1, y1, dir1;
        int x2, y2, dir2;
        int steps;
    };
    
    int main() {
        ios::sync_with_stdio(false);
        cin.tie(0);
        
        int N, C;
        // Read input
        // Assuming the first line contains N and C (though C is not used in the description)
        // But based on description, the first line only contains N
        cin >> N;
        // Read N lines of the maze
        vector<string> maze(N);
        for(int i=0;i<N;i++) {
            cin >> maze[i];
        }
        
        // Function to check if a cell is valid
        auto isValid = [&](int x, int y) -> bool {
            if(x < 0 || x >= N || y < 0 || y >= N) return false;
            if(maze[x][y] == '#') return false;
            return true;
        };
        
        // Starting positions (0-indexed)
        int start_x = N-1;
        int start_y = 0;
        
        // Target position
        int target_x = 0;
        int target_y = N-1;
        
        // Initialize BFS
        queue<State> q;
        
        // Initial directions: up (0) and right (1)
        State startState;
        startState.x1 = start_x;
        startState.y1 = start_y;
        startState.dir1 = 0; // Up
        startState.x2 = start_x;
        startState.y2 = start_y;
        startState.dir2 = 1; // Right
        startState.steps = 0;
        
        q.push(startState);
        
        // To encode visited states, use a bitset or a hash set
        // Given the large state space, using a hash set is more feasible
        // We'll encode the state into a unique number
        // Combine all variables into a single key
        // key = x1 * N * 4 * N * 4 + y1 * 4 * N *4 + dir1 * N *4 + x2 *4 + y2 *4 + dir2
        // To prevent overflow, use a separate unordered_set with a custom hash
        // Alternatively, use a string as key
        unordered_set<string> visited;
        // Encode initial state
        auto encode = [&](const State& s) -> string {
            return to_string(s.x1) + "," + to_string(s.y1) + "," + to_string(s.dir1) + "|" +
                   to_string(s.x2) + "," + to_string(s.y2) + "," + to_string(s.dir2);
        };
        
        visited.insert(encode(startState));
        
        while(!q.empty()) {
            State current = q.front();
            q.pop();
            
            // Check if both paths have reached the target
            bool reached1 = (current.x1 == target_x && current.y1 == target_y);
            bool reached2 = (current.x2 == target_x && current.y2 == target_y);
            if(reached1 && reached2) {
                cout << current.steps;
                return 0;
            }
            
            // Try all three commands: Forward, Left, Right
            for(int cmd=0; cmd<3; cmd++) {
                State next = current;
                // Apply command to path1 (starting direction up)
                if(cmd == 0) { // Forward
                    int nx1 = next.x1 + dx[next.dir1];
                    int ny1 = next.y1 + dy[next.dir1];
                    if(isValid(nx1, ny1)) {
                        next.x1 = nx1;
                        next.y1 = ny1;
                    }
                    // Else, ignore the command for this path
                }
                else if(cmd == 1) { // Left
                    next.dir1 = (next.dir1 + 3) % 4;
                }
                else if(cmd == 2) { // Right
                    next.dir1 = (next.dir1 + 1) % 4;
                }
                
                // Apply command to path2 (starting direction right)
                if(cmd == 0) { // Forward
                    int nx2 = next.x2 + dx[next.dir2];
                    int ny2 = next.y2 + dy[next.dir2];
                    if(isValid(nx2, ny2)) {
                        next.x2 = nx2;
                        next.y2 = ny2;
                    }
                    // Else, ignore the command for this path
                }
                else if(cmd == 1) { // Left
                    next.dir2 = (next.dir2 + 3) % 4;
                }
                else if(cmd == 2) { // Right
                    next.dir2 = (next.dir2 + 1) % 4;
                }
                
                // Increment steps
                next.steps = current.steps + 1;
                
                // Encode the new state
                string key = encode(next);
                if(visited.find(key) == visited.end()) {
                    visited.insert(key);
                    q.push(next);
                }
            }
        }
        
        // If no solution found
        cout << -1;
        return 0;
    }
    

    Explanation of the Code

    1. Reading Input:

      • The maze is read as an N x N grid where each cell is either '.' (empty) or '#' (obstacle).
    2. State Initialization:

      • The initial state is set with Bờm at (N-1, 0) (0-indexed) facing up (0) and right (1) for both possible starting directions.
    3. BFS Queue:

      • We use a BFS queue to explore all possible sequences of commands.
      • Each state in the queue represents the positions and directions for both starting scenarios, along with the number of steps taken so far.
    4. Visited States:

      • To prevent revisiting states, we use an unordered_set with a unique string key representing the combined state of both paths.
    5. Command Execution:

      • For each state, we try applying the three possible commands (Forward, Left, Right) to both paths.
      • We calculate the new positions and directions after each command.
      • If both paths reach the target (1, N), we output the number of steps taken.
    6. Termination:

      • The BFS continues until a valid sequence is found or all possible states are exhausted.

    Example Execution

    Consider the provided example:

    Input:

    3
    .#.
    ...
    ...
    

    Output:

    9
    

    The BFS will explore all possible command sequences and determine that the minimal number of commands required for both initial directions to reach (1, 3) is 9, as demonstrated in the example.

    Conclusion

    This solution effectively uses BFS to explore all viable command sequences while accounting for both possible initial directions. By tracking visited states and efficiently encoding them, it ensures that the search remains efficient even for larger mazes. The approach guarantees finding the minimal number of commands required for Bờm to escape the maze successfully.