A. Shortest Path with Obstacle

문제 설명 :

There are three cells on an infinite 2-dimensional grid, labeled A, B, and F. Find the length of the shortest path from A to B if:

in one move you can go to any of the four adjacent cells sharing a side;
visiting the cell F is forbidden (it is an obstacle).

주어진 a, b, f좌표가 있는데 f는 피하면서 가장 짧은 a - > b로의 거리를 찾는 문제였다.

틀린 이유

처음에 가장 짧은이면서 그래프가 나오길래 흥분해서 bfs로 했다.
시간초과가 발생하였다
그 이유는 t가 10^4이고 맵이 1,000 1,000이기에 10^9 -> 10억이라서 바로 터졌다..

풀이방법 :

아주 간단했다 그냥 x차이 y차이를 고려하고
예외인경우를 처리 해주면 끝난다

예외인 경우 ->

이 그림에서 일직선이 있는데 일직선상에서 장애물이 있을경우 돌아서 가야하니 +2를 처리해주면 되는 것이다..

a - > b로 가는길에 장애물이 있는경우 or b -> a로 가는길에 장애물이 있는경우
이것이 일직선일 경우

if(xa == xb && xb == xf) {
    if(min(ya, yb) < yf && yf  <= max(ya, yb)) {
        ans +=2
        }
   }

세로인 경우

//세로 예외처리 
        if (ya == yb && yb == yf) {
            if (min(xa, xb) <= xf && xf <= max(xa, xb)) {
                ans += 2;
            }
        }