Untitled

 avatar
unknown
plain_text
a year ago
2.6 kB
3
Indexable
#include<iostream>
using namespace std;

int T, N, M, arr[50][50], visited[50][50];
int Answer, startX, startY, endX, endY;

int dxr[4] = { 0, 0, 1, -1 };
int dyr[4] = { 1, -1, 0, 0 };
int dxc[2] = { 1, -1 };
int dyc[2] = { 0, 0 };

const int MAX = 10000;
struct Queue {
    int rear, front;
    int queue[MAX];
    Queue() {
        front = rear = -1;
    }

    void push(int value) {
        queue[++rear] = value;
    }

    int pop() {
        return queue[++front];
    }
    bool isEmpty() {
        return front == rear;
    }
};

bool isValid(int x, int y) {
    return x >= 0 && x < N && y >= 0 && y < M;
}

void bfs(int x, int y, int dist) {
    Queue q;
    q.push(x);
    q.push(y);
    q.push(dist);

    while (!q.isEmpty()) {
        int r = q.pop();
        int c = q.pop();
        int ndist = q.pop();

        if (arr[r][c] == 3) {
            cout << ndist << " ";
            if (Answer > ndist) {
                Answer = ndist;
            }
        }
        // duyet hang ngang
        for (int i = 0; i < 4; i++) {
            int nx = r + dxr[i];
            int ny = c + dyr[i];

            if (isValid(nx, ny) && arr[nx][ny] == 1 && visited[nx][ny] == 0) {
                visited[nx][ny] = 1;
                q.push(nx);
                q.push(ny);
                q.push(ndist);
            }
        }
        // duyet hang doc
        for (int i = 0; i < 2; i++) {
            for (int k = 1; k <= N && k < Answer; k++) {
                int nx = r + k * dxc[i];
                int ny = c + k * dyc[i];

                if (isValid(nx, ny) && arr[nx][ny] == 1 && visited[nx][ny] == 0) {
                    if (ndist < k - 1) {
                        ndist = k - 1;
                    }
                    visited[nx][ny] = 1;
                    q.push(nx);
                    q.push(ny);
                    q.push(ndist);
                    break;
                }
            }
        }
    }
}

int main() {
    freopen("Mario.txt", "r", stdin);
    cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        Answer = 999;
        cin >> N >> M;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                cin >> arr[i][j];
                if (arr[i][j] == 2) {
                    startX = i;
                    startY = j;
                }
            }
        }
        // Reset visited array
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                visited[i][j] = 0;
            }
        }
        bfs(startX, startY, 1);
        cout << "Case #" << tc << endl;
        cout << Answer << endl;
    }
    return 0;
}
Editor is loading...
Leave a Comment