문제
택시 거리는 바둑판 모양의 도로망을 가진 도시에서 점 A에서 B까지의 최단 거리를 구할 경우 도로를 따라서만 가는 가장 짧은 거리를 뜻한다.
위의 사진에서는 빨간색 선이 택시거리이다. 즉, 점 A의 좌표가 (x1, y1)이고 점 B의 좌표를 (x2, y2)라고 했을 때, 두 장소 사이의 택시 거리 D는 다음과 같다.
D=|x2−x1|+|y2−y1|
인접한 0과 0, 0과 1, 1과 1 사이의 거리를 1이라고 할 때, 두 1 사이의 거리를 구하는 프로그램을 작성하시오.
입력
첫 줄엔 문자열의 높이 N과 가로 M이 주어진다. (2 ≤ N, M ≤ 1,000) 이다.
두 번째 줄부터 M개의 숫자 0또는 1이 예제 입력과 같이 N개의 줄에 걸쳐 입력된다.
1는 항상 두 개만 입력된다.
출력
주어진 숫자들에서 1과 1사이의 택시 거리를 구하시오.
예제 입력 1
3 4 1 0 0 0 0 0 0 0 0 0 0 1 |
예제 출력 1
5 |
더보기
Solution
#include<stdio.h>
#include<stdbool.h>
int main(void)
{
int N, M, start[2], end[2], temp;
bool started=false;
scanf("%d %d", &N, &M);
for(int n=0;n<N;n++)
for(int m=0;m<M;m++)
{
scanf("%d", &temp);
if(temp==1)
{
if(!started)
{
start[0]=n;
start[1]=m;
started=true;
}
else
{
end[0]=n;
end[1]=m;
break;
}
}
}
for(int i=0;i<2;i++)
{
end[i]-=start[i];
end[i]=end[i]<0?-end[i]:end[i];
}
printf("%d\n", end[0]+end[1]);
return 0;
}
728x90
'백준 알고리즘' 카테고리의 다른 글
<백준 알고리즘> 13116번: 30번 (0) | 2021.01.02 |
---|---|
<백준 알고리즘> 17945번: 통학의 신 (0) | 2021.01.02 |
<백준 알고리즘> 20492번: 세금 (0) | 2020.12.30 |
<백준 알고리즘> 10181번: Federation Favorites (0) | 2020.12.30 |
<백준 알고리즘> 14782번: Bedtime Reading, I (0) | 2020.12.30 |