Untitled
unknown
plain_text
2 years ago
1.7 kB
5
Indexable
// In Practice, You should use the statndard input/output // in order to receive a score properly. // Do not use file input and output. Please be very careful. #include<iostream> using namespace std; int n, m ,p,q, s,t; #define size 10000000 int queue[size]; int front =-1; int rear=-1; int map[205][205]; int dx[4]={-1,-1,1,1}; int dy[4]={-1,1,-1,1}; int visit[205][205]; int ans; bool isEmpty(){ return front == rear ; } void push(int x){ if(rear == size -1) rear=-1; rear ++; queue[rear]=x; } int pop(){ if(front == size -1) front =-1; front ++; return queue[front]; } void reset(){ for(int i=0 ; i<205; i++){ for( int j=0 ; j< 205 ; j++){ map[i][j]=0; visit[i][j]=-1; } } } void bfs( int x, int y){ front=rear=-1; push(x); push(y); visit[x][y] = 0; while(!isEmpty()){ int x1=pop(); int y1=pop(); for( int i = 0; i<4; i++){ int x2= x1+dx[i]; int y2= y1+dy[i]; while(x2 >= 1 && x2 <= n && y2 <= n && y2 >= 1 && map[x2][y2] == 0) { if( visit[x2][y2] == -1) { visit[x2][y2]= visit[x1][y1] + 1; push(x2); push(y2); } if( x2== s && y2 ==t) return ; x2+=dx[i]; y2+=dy[i]; } } } } int main(int argc, char** argv) { int test_case; int T; //freopen("text.txt", "r", stdin); cin >> T; /* Read each test case from standard input. */ for(test_case = 1; test_case <= T; ++test_case) { ans = -1; reset(); cin>>n>>m>>p>>q>>s>>t; for(int i=0 ; i<m; i++){ int a,b; cin>>a>>b; map[a][b]=1; } bfs(p,q); cout << visit[s][t] << endl; } return 0;//Your program should return 0 on normal termination. }
Editor is loading...