Untitled

 avatar
user_1164828
plain_text
5 months ago
2.1 kB
1
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;
}
Leave a Comment