Question

QUATU2 - Quân tượng đi lạc Dữ liệu vào: standard input Dữ liệu ra: standard output Giới hạn thời gian: 1.0 giây Giới hạn bộ nhớ: 128 megabyte Có một quân tượng trong cờ tướng đi lạc vào một bàn cờ vua. Bàn cờ vua có kích thước là 8 x 8, các dòng được đánh số từ 1 đến 8 theo thứ tự từ trên xuống dưới, các cột được đánh số từ 1 đến 8 theo thứ tự từ trái qua phải. Quân tượng đi lạc đang nằm ở ô (y, x), dòng y cột x. Để có thể quay trở lại bàn cờ tướng, quân tượng phải tìm cách di chuyển đến một cổng thoát tại ô (ty, tx) trên bàn cờ vua. Bạn hãy tính xem quân tượng phải di chuyển ít nhất bao nhiêu nước đi để đến được cổng thoát này. Ghi chú: Quân tượng cờ tướng di chuyển theo đường chéo 2 ô một, từ ô (y, x) có thể đi đến một trong bốn ô (y-2, x-2), (y-2, x+2), (y+2, x-2), (y+2, x+2). Dữ liệu nhập: - Là bốn số nguyên y, x, ty, tx mỗi số cách nhau một khoảng trắng (1 y, x, ty, tx 8) Dữ liệu xuất: - Nếu quân tượng không thể di chuyển đến cổng thoát, mãi mãi ở lại bàn cờ vua, in ra -1. - Nếu quân tượng có thể di chuyển đến cổng thoát, in ra số bước di chuyển ít nhất. Ví dụ input 1 1 1 2 output -1 input 3 5 7 5 output 2

Answer 1

Tham Khảo:

#include <bits/stdc++.h>

using namespace std;

bool v(int y, int x) {

return 1 <= y && y <= 8 && 1 <= x && x <= 8;

}

int m(int y, int x, int ty, int tx) {

if (!v(y, x) || !v(ty, tx)) {

return -1;

}

deque<pair<int, pair<int, int>>> q;

q.push_back({y, {x, 0}});

bool vis[9][9] = {false};

vis[y][x] = true;

int dx[] = {-2, -2, 2, 2};

int dy[] = {-2, 2, -2, 2};

while (!q.empty()) {

int cy = q.front().first;

int cx = q.front().second.first;

int s = q.front().second.second;

q.pop_front();

if (cy == ty && cx == tx) {

return s;

}

for (int i = 0; i < 4; ++i) {

int ny = cy + dy[i];

int nx = cx + dx[i];

if (v(ny, nx) && !vis[ny][nx]) {

q.push_back({ny, {nx, s + 1}});

vis[ny][nx] = true;

        }

    }

}

return -1;

}

int main() {

int y, x, ty, tx;

cin >> y >> x >> ty >> tx;

cout << m(y, x, ty, tx) << endl;

return 0;

}