2019 CNUPC 전북대학교 프로그래밍 대회 문제 - 택시 거리(C++)

안녕하세요, 츄르 사려고 코딩하는 집사! 코집사입니다.

 

2019 CNUPC 전북대학교 프로그래밍 대회 문제 - 택시 거리(C++)

1. 문제

택시 거리는 바둑판 모양의 도로망을 가진 도시에서 점 A에서 B까지의 최단 거리를 구할 경우 도로를 따라서만 가는 가장 짧은 거리를 뜻한다.

위의 사진에서는 빨간색 선이 택시거리이다. 즉 택시 거리는 D 를 두 장소 사이의 택시 거리라고 할 때

 

D= x2-x1+ y2-y1

D=|x 2 −x 1 |+|y 2 −y 1 | D=|x2−x1|+|y2−y1|

을 택시거리라고 한다.

 

이 택시거리를 이용해 근접한 0와 0, 1와 0, 1와 1 사이의 거리를 1이라고 할 때 두 x 사이의 거리를 구하는 프로그램을 만들어라.

 

 

2. 입력

첫 줄엔 문자열의 높이 N N 과 너비 M M 이 주어진다. (2≤N,M≤1000) 2≤N,M≤1000) 이다.

두 번째 줄부터 M개의 숫자 0또는 1이 N 줄 동안 입력된다.

1는 반드시 두 개가 입력된다.

3 4

1 0 0 0

0 0 0 0

0 0 0 1

 

 

3. 출력

주어진 숫자들에서 1와 1사이의 거리를 구하시오.

5

 

 

 

4. 문제 풀이

1이 있는 좌표를 빼서 절대값을 취해 리턴하면 됩니다.

 

 

 

5. 소스 코드

#include<iostream>

#include<string>

#include<cmath>

using namespace std;

int main(){

 

    int n,m;

    int x1=0,y1=0;

    int x2=0,y2=0;

    cin>>n>>m;

    int arr[n][m];

    for(int i=0 ;i<n; i++){

        for(int j=0; j<m; j++){

            cin>>arr[i][j];

            if(arr[i][j]==1) {

                x1=i;

                y1=j;

            }

        }

    }

 

    for(int i=0;i<=x1;i++)

    {

        if(i!=x1)

        {

            for(int j=0;j<m;j++)

            {

                if(arr[i][j]==1)

                {

                    x2=i;

                    y2=j;

                }

            }

        }

        else

        {

            for(int j=0;j<y1;j++)

            {

                if(arr[i][j]==1)

                {

                    x2=i;

                    y2=j;

                }

            }

        }

    }

    cout<<abs((x2-x1))+abs((y2-y1));

}

 

 

6. 결과