Untitled
user_1164828
plain_text
a year ago
2.1 kB
8
Indexable
//taiii
//Fast robottt
#include<iostream>
using namespace std;
char map[205][205];
int cnt[205][205];
int visited[205][205];
int N,M, xStart, yStart, xTarget, yTarget;
int start, last, xNext, yNext;
int xQueue[1000000];
int yQueue[1000000];
int dx[] = {1,0,0,-1};
int dy[] = {0,1,-1,0};
void BFS(){
int xCur, yCur;
start = 0;
last = 0;
xQueue[last] = xStart;
yQueue[last++] = yStart;
while(start != last){
xCur = xQueue[start];
yCur = yQueue[start++];
for(int i=0; i<4; i++){
xNext = xCur + dx[i];
yNext = yCur + dy[i];
if(xNext >=0 && xNext < M && yNext >=0 && yNext <N && visited[xNext][yNext] == 0 && map[xNext][yNext] != '1'){
if(dx[i] == 1){
int k = 0;
while(xNext >=0 && xNext < M && map[xNext + k][yNext] != '1'){
cnt[xNext+k][yNext] = cnt[xCur][yCur] + 1;
k+=dx[i];
visited[xNext][yNext] = 1;
}
}
if(dx[i] == -1){
int k = 0;
while(xNext >=0 && xNext < M && map[xNext + k][yNext] == '0'){
cnt[xNext+k][yNext] = cnt[xCur][yCur] + 1;
k+= dx[i];
visited[xNext][yNext] = 1;
}
}
if(dy[i] == 1){
int k = 0;
while(yNext >=0 && yNext < N && map[xNext][yNext + k] != '1'){
cnt[xNext][yNext+k] = cnt[xCur][yCur] + 1;
k+= dy[i];
visited[xNext][yNext] = 1;
}
}
if(dy[i] == -1){
int k = 0;
while(yNext >=0 && yNext < M && map[xNext][yNext+k] != '1'){
cnt[xNext][yNext+k] = cnt[xCur][yCur] + 1;
k+= dy[i];
visited[xNext][yNext] = 1;
}
}
if(xNext == xTarget && yNext == yTarget){
return;
}
xQueue[last] = xNext;
yQueue[last++] = yNext;
}
}
}
}
int main(){
freopen("Text.txt", "r", stdin);
int T;
cin >>T;
for(int tc = 1; tc <=T; tc++){
cin >> N >> M;
cin >> yStart >> xStart >> yTarget >> xTarget;
for(int i=0; i<M; i++){
cin >> map[i];
for(int j=0;j<N;j++){
visited[i][j] = 0;
cnt[i][j] = 0;
}
}
BFS();
cout << cnt[xTarget][yTarget] << endl;
}
return 0;
}Editor is loading...
Leave a Comment