Untitled
unknown
plain_text
2 years ago
1.8 kB
3
Indexable
#include<iostream> using namespace std; typedef struct { int x,y; }o_xy; int T; int N; // so hang int M; // so quan dich int map[205][205]; o_xy queue[1000000]; int visited[205][205]; int r = -1, f = -1; int dx[4] = {-1,-1,1,1}; int dy[4] = {-1,1,1,-1}; void push(o_xy obj) { r++; queue[r] = obj; } void pop(o_xy &obj) { f++; obj = queue[f]; } bool isSafe(o_xy obj) { if(obj.x >= 1 && obj.x <= N && obj.y >= 1 && obj.y <= N) return true; return false; } void BFS(o_xy pre) { r= f = -1; push(pre); visited[pre.x][pre.y] = 0; while(r != f) { pop(pre); for(int i = 0; i < 4; i++) { o_xy next; next.x = pre.x; next.y = pre.y; while(1) { next.x += dx[i]; next.y += dy[i]; if(!isSafe(next) || map[next.x][next.y] == 1) break; if(visited[next.x][next.y] == -1) { push(next); visited[next.x][next.y] = visited[pre.x][pre.y] + 1; } else if(visited[next.x][next.y] > visited[pre.x][pre.y] + 1) { visited[next.x][next.y] = visited[pre.x][pre.y] + 1; } } } } } void reset() { r = f =-1; for(int i = 0; i < 205; i++) for(int j = 0; j < 205; j++) visited[i][j] = -1; for(int i = 0; i < 205; i++) for(int j = 0; j < 205; j++) map[i][j] = 0; } int main() { freopen("Text.txt","r",stdin); cin>>T; for(int tc = 1; tc <= T; tc++) { reset(); cin>>N>>M; int x_start, y_start, x_end, y_end; cin>>x_start>>y_start>>x_end>>y_end; for(int i = 0; i < M; i++) { int x,y; cin>>x>>y; map[x][y] = 1; } o_xy start; start.x = x_start; start.y = y_start; BFS(start); cout<<visited[x_end][y_end]<<endl; } return 0; }
Editor is loading...