Untitled
//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