Untitled

mail@pastecode.io avatar
unknown
plain_text
a month ago
2.7 kB
0
Indexable
Never
#include <iostream>
#include <stdio.h>
#define MAX 201
#define WALL '1'
using namespace std;
int T;
int n, m;
char a[MAX][MAX];
int startX, startY, endX, endY;
int moveY[] = {0,0,-1,1};
int moveX[] = {-1,1,0,0}; //4 hướng đi lần lượt là: trái, phải, lên, xuống
int cost[MAX][MAX]; //chi phí để đi đến từng ô
struct Point {
int x,y;
};
Point myQueue[1000000];
int front, rear;
void initQueue() {
front = rear = -1;
}
void enQueue(Point p) {
rear++;
myQueue[rear] = p;
}
Point deQueue() {
front++;
Point temp = myQueue[front];
if(front==rear) front=rear=-1;
return temp;
}
bool isQueueEmpty() {
return front==-1 && rear==-1;
}
void input() {
cin >> m >> n; //n = số hàng, m = số cột
cin >> startY >> startX >> endY >> endX;
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
cin >> a[i][j];
cost[i][j] = -1;
}
}
}
bool checkValidCell(int x, int y) {
if(x < 1 || x > n || y < 1 || y > m) return false;
if(a[x][y] == WALL) return false;
return true;
}
void printCost() {
cout << "print cost...\n";
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
printf("%2d ", cost[i][j]);
}
cout << endl;
}
cout << endl;
}
bool checkIfAllCellsVisited() {
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
if(cost[i][j] == -1) return false;
}
}
return true;
}
void fastRobot() {
Point startPosition;
startPosition.x = startX;
startPosition.y = startY;
enQueue(startPosition);
cost[startX][startY] = 0;
int nextX, nextY;
while(!isQueueEmpty()) {
Point currPos = deQueue(); //current position
int currX, currY;
//loang ra 4 hướng xung quanh, loang cho tới khi gặp tường
//hoặc quá kích thước của mê cung thì dừng, chứ ko phải
//loang từng ô
for(int i=0; i<4; i++) {
currX = currPos.x;
currY = currPos.y;
while(1) {
nextX = currX + moveX[i];
nextY = currY + moveY[i];
if(!checkValidCell(nextX, nextY)) break;
if(cost[nextX][nextY] == -1) {
cost[nextX][nextY] = cost[currPos.x][currPos.y] + 1;
Point p2;
p2.x = nextX; p2.y = nextY;
enQueue(p2);
} else {
//Nếu gặp ô mà cost[nextX][nextY] != -1 thì chứng tỏ
//ô này đã được thăm rồi. ta vẫn tiếp tục đi tiếp chứ ko đc break.
//chỉ có điều là ko cho ô này vào queue
//Do đó trong này ko làm j cả
}
currX = nextX; currY = nextY;
}
}
}
}
int main() {
freopen("FastRobot_input.txt", "r", stdin);
cin >> T;
for(int tc = 1; tc <= T; tc++) {
input();
fastRobot();
if(cost[endX][endY] != -1) {
cout << cost[endX][endY]-1 << endl;
} else {
//ko tìm đc đường tới đích
cout << "-1\n";
}
//printCost();
}
}
Leave a Comment