[Codeforces][Round #731][Div.3] A : Shortest Path with Obstacle (C++)

https://codeforces.com/contest/1547/problem/A

Problem - A - Codeforces

 

 

 

[난이도] Div.3
[유형] 구현

[풀이]
tc가 10^4인걸 생각 못하고 BFS로 풀었다가 TLE를 맞았습니다.
A,B,F가 모두 다른 점이므로 O(1)에 계산이 가능하다는 것을 파악해야합니다.
만약 A,B,F가 일직선상에 있지 않다면 최단거리가 여러 가지이므로 F에 의해 한 경로가 막힌다 하더라도
다른 경로를 이용하면 되므로 무조건 dist(A,B) 만큼이 최단 거리가 됩니다.

만약 A,B,F가 일직선 상에 있고 A,B 사이에 F가 있다면 유일한 최단 거리 dist(A,B)가 막힌 것이므로
F를 피해서 가는 이동 2를 더해줘야 하므로 dist(A,B)+2가 정답이 됩니다.

 

 

#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;

int tc,sy,sx,ey,ex,fy,fx;
bool visit[1001][1001];

bool same(int a,int b,int c){
    return (a==b&&b==c);
}
bool between(int a,int b,int c){
    if(a>c) swap(a,c);
    return (a<b&&b<c);
}
int main(){
    scanf("%d",&tc);
    while(tc--){
        scanf("%d%d%d%d%d%d",&sx,&sy,&ex,&ey,&fx,&fy);
        int ans = abs(sx-ex)+abs(sy-ey);
        if(same(sx,fx,ex)&&between(sy,fy,ey) || same(sy,fy,ey)&&between(sx,fx,ex)){
            ans+=2;
        }
        printf("%d\n",ans);
    }
}

 

https://github.com/has2/Problem-Solving/blob/master/codeforces/Round731-Div.3/A.cpp