Queen's Attack 2 : Chess game - 코드분석

Study/알고리즘2019.01.10 18:51

Sample Input 1

5 3
4 3
5 5
4 2
2 3

체스보드는 5X 5  여왕의 위치 ( 4, 3)  / 장애물 좌표 (5,5) (4,2) (2,3)


1)    모서리 거리 구하기 

    // distance to edges
  int tSpan = n-rQueen;
  int lSpan = cQueen-1;
  int bSpan = rQueen-1;
 int rSpan = n-cQueen;

   // distance to corners
  int blSpan = min (cQueen, rQueen) -1;
  int brSpan = min (rQueen-1, n-cQueen);
  int tlSpan = min (n-rQueen, abs(1-cQueen));
  int trSpan = n - max(cQueen, rQueen);

 tSpan = 5 – 4 = 1
lSpan = 3 – 1 = 2
bSpan = 4 – 1 = 3
rSpan = 5 – 3 = 2

blSpan = min(3, 4) -1 = 2
brSpan = min(3, 2) = 2
tlSpan = min(1, 2) = 1
trSpan = 5  - max(3,4) = 5 – 4 =1


❏ 여왕의 위치 ( 4, 3 ) , 장애물 좌표 (5,5) (4,2) (2,3) , k = 3  
 tSpan = 1   lSpan = 2   bSpan =  3  rSpan = 2
blSpan = 2  brSpan = 2   tlSpan = 1   trSpan = 1

①    [ 5,5 ]
조건 1 : rObstacle = rQueen   (same row)
5 ≠ 4  -->  skip

조건 2 : cObstacle = cQueen   (same col)
5 ≠ 3    -->  skip

조건 3 :  abs(cQueen-cObstacle) = abs(rQueen-rObstacle)  / same diagonal
abs(3 – 5) ≠  abs(4 – 5)  skip


②    [ 4, 2 ]
조건 1 : rObstacle = rQueen   (same row)
4 = 4    -->  go on
· cObstacle > cQueen  (2 > 3)          skip
     rSpan = min (rSpan, cObstacle-cQueen-1);
· cObstacle < cQueen  (2 < 3)  OK
    lSpan = min (lSpan, cQueen-cObstacle-1);        // lSpan = min(2, 3 – 2 -1 ) = min(2, 0) = 0

조건 2 : cObstacle = cQueen   (same col)    2 ≠ 3   skip
조건 3 :  abs(cQueen-cObstacle) = abs(rQueen-rObstacle)  / same diagonal
abs(3 – 2) ≠  abs(4 – 4)  skip

③    [ 2, 3 ]
조건 1 :   rObstacle = rQueen
2 ≠ 4    -->  skip
조건 2 :   cObstacle = cQueen   3 = 3
·  rObstacle > rQueen  (2 > 4)    skip
·  rObstacle < rQueen  (2 < 4)
       bSpan = min (bSpan, rQueen-rObstacle-1);
    bSpan = min(3, 4 – 2 -1) = min(3, 1) = 1

조건 3 :  abs(cQueen-cObstacle) = abs(rQueen-rObstacle)  / same diagonal
     abs(3 – 3) ≠  abs(4 – 2)  skip
 
❏ 공격할 수 있는 원의 개수 구하기 


 tSpan = 1   lSpan = 0   bSpan =  1  rSpan = 2
blSpan = 2  brSpan = 2   tlSpan = 1   trSpan = 1

tSpan+rSpan+bSpan+lSpan+blSpan+brSpan+trSpan+tlSpan

1 + 2 + 0 + 1 + 2 + 2 + 1 + 1  = 10



작성자

Posted by 비타오백

관련 글

댓글 영역

티스토리 툴바