Queen's Attack 2 : Chess game - 생각하기

Study/알고리즘2019.01.10 17:34

Sample Input 1

5 3
4 3
5 5
4 2
2 3

Sample Output 1

10


접근방식

이 문제를 보고 대략난감했다.  2D 배열에 넣어서 비교하는 식으로 구현하면 된다.
뭔가 복잡하다. 좌표의 위치를 맞는 조건에 맞는 값의 개수를 새면 될것 같다..

너무 어려워서 커뮤니티 글을 보고 힌트를 얻었다.
카운트 가장자리 거리를 측정 한 다음 장애물이 여왕과 동일한 대각선 / 수평 / 수직을 공유하는지 확인하십시오.
대각선 거리는 까다로울 수 있지만 기본적으로 수평 / 수직 거리를 찾는 것과 같으며
가장 낮은 것을 선택하는 것과 같습니다. 가장 단순한 것은 왼쪽 아래에 있습니다.
기본적으로 Queen의 좌표 -1이므로 int blSpan = min (cQueen , rQueen) -1;

새로운 장애물 좌표를 얻을 때마다이 값을 업데이트하는 방법을 생각하면 시간을 할애 할 것입니다.
동일한 행 / 열 / 대각선에 있는지 확인하십시오. 대각선 역시 까다 롭습니다.
그러나 모든 대각선 장애물은 여왕으로부터 동일한 행 / 열 거리를 가질 것입니다. abs 값을 얻으십시오.

pre-processing. count edge distance then check if obstacles share the same diagonal / horizontal / vertical with Queen.
Diagonal distances might be tricky, however it is basically the same as finding horizontal/vertical distance and than choosing which is lowest: the most trivial is bottom-left since it is basically the coordinate of the Queen
minus 1: int blSpan = min (cQueen, rQueen) -1;

than you'll spend some time figuring out how to update these values every time you get new obstacle coordinate.
check if it's in the same row/column/diagonal. Diagonal is tricky too, however the thing is that all diagonal obstacles will have equal row/column distance from Queen. Just get the abs value.












작성자

Posted by 비타오백

관련 글

댓글 영역

티스토리 툴바