메두사와 전사들

https://www.codetree.ai/training-field/frequent-problems/problems/medusa-and-warriors/description?page=1&pageSize=10

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

어디가 틀린건지 모르겠다..

 

 

 

내가 틀린 케이스

입력

50 189
44 35 33 1
29 48 1 28 19 10 7 38 5 45 30 2 40 14 29 47 7 12 16 30 27 8 47 22 35 31 16 29 10 11 13 33 20 46 6 44 45 36 24 12 42 33 48 32 14 11 17 23 27 43 25 5 39 32 31 47 33 37 2 45 6 17 21 6 18 44 40 7 22 1 43 4 1 12 46 38 27 26 1 31 0 27 47 11 38 2 12 21 25 47 46 41 1 38 48 20 5 43 15 19 5 38 1 3 25 1 44 28 45 29 21 20 6 39 7 32 34 21 19 20 24 18 46 6 31 16 24 43 42 43 40 48 2 15 7 37 29 33 37 41 1 32 20 13 36 35 34 43 7 29 11 22 34 6 49 25 14 1 40 30 46 24 18 0 8 42 42 31 8 49 0 24 28 27 41 21 43 16 17 3 5 13 44 22 34 39 21 10 2 21 39 15 34 46 36 26 11 10 10 17 34 0 30 49 11 36 15 5 20 44 42 14 4 46 38 43 9 5 37 25 10 2 24 23 19 3 49 26 36 16 46 33 11 48 17 36 11 40 49 42 19 45 17 13 38 1 2 18 39 18 9 25 27 41 9 22 12 33 40 18 17 21 22 43 5 2 30 5 42 22 14 29 38 39 5 17 24 2 49 2 3 23 3 44 42 46 10 44 4 4 15 7 18 49 5 49 7 42 27 33 5 24 8 45 41 12 21 8 47 9 26 33 49 19 2 29 36 6 30 12 3 32 18 3 43 15 2 31 16 11 40 19 5 47 44 44 31 30 28 48 41 28 17 1 4 48 12 0 30 23 37 38 25 9 45 43 36 46 6 11 42 35 27 2 29 9 0 14 37 22 49 34 48 21 8 4 14 20
0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0
0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0
1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0
0 1 1 0 0 0 0 1 0 1 1 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0 1
0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0
0 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0
0 1 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 1 0 0 0 0 1 1
0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1
1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 1 0
0 0 1 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 0 0 1 0 0 0 0 0
0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0 1 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1
0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 1 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 1 1 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 1 0
0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 1
0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 1 1 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0
0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 1 0 0 0 0 1 0 0 1 0 0
1 0 0 1 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 1 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0
0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0
0 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0
0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0
0 1 0 1 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 0 0 1 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 0

 

 

3번째 턴에서

 

메두사 위치 : (42, 34)  일때

 

warriorCnt[][] : warrior의 위치, 갯수를 나타내는 2차원 배열

 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 2 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0
 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 1 0 1 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0
 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0
 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0
 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0
 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0
 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 2 0 1 1 1 1 0 0 3 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 1 1 0 1 0 1 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

메두사 시선 : 메두사의 시선과 warrior로 인한 그림자를 나타내는 2차원 배열

 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
-1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
-1-1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
-1-1-1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
-1-1-1-1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
-1-1-1-1-1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
-1-1-1-1-1-1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
-1-1-1-1-1-1-1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
-1-1-1-1-1-1-1-1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
-1-1-1-1-1-1-1-1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
-1-1-1-1-1-1-1-1-1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
-1-1-1-1-1-1-1-1-1-1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
-1-1-1-1-1-1-1-1-1-1-1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
-1-1-1-1-1-1-1-1-1-1-1-1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
-1-1-1-1-1-1-1-1-1-1-1-1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
-1-1-1-1-1-1-1-1-1-1-1-1-1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
-1-1-1-1-1-1-1-1-1-1-1-1-1-1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

 

 

돌로 변한 warrior의 수는 7이 나와야 하는데 내 코드에선 8이 나온다..

 

그림판으로 위 출력에 대해 그려보았는데 8이 나온다.

 

돌로 변한 warrior를 세는 로직, 그림자를 만드는 로직은 틀리지 않았다는 뜻인데

 

그러면 warrior가 메두사에게 가는 로직이 틀렸거나

warrior가 공격하는 로직이 틀렸거나

메두사가 warrior를 공격하는 로직이 틀렸거나

메두사가 최단경로로 가는 로직이 틀렸거나 ?

 

어디가 틀린거지

 

 

알게된 점

• bfs를 활용하여 최단경로를 구하는 방법
  • prev 배열을 둬서 이전 방문 위치를 저장하여 구할 수 있다.
  • 또는 배열에 최단경로 cnt값을 기록한 뒤 cnt를 1씩 감소시키면서 경로를 역 추적할 수 있다.
• 클래스를 만들지 않고, 여러 좌표 배열 변수를 통해서 상태를 확인할 수 있다.
  • warrior 클래스에 돌로 변하는 여부를 확인하는 멤버변수를 두지 않고 warrior의 좌표를 이용한 sightMap[][] 변수에 접근하여 돌로 변하는 여부를 확인할 수 있다.
• 클래스의 좌표를 이용하여 상태를 나타낼 수 있다.
  • 위 문제에서는 Warrior의 좌표가 -1이면 사망한 상태

import java.util.*;
import java.io.*;

class Warrior{
    int r,c;

    public Warrior(int r,int c){
        this.r = r;
        this.c = c;
    }
}
public class Main {

    static int N,M;
    static int[][] map;
    static int[][] warriorCnt;
    static Warrior[] warriors;
    static int[] medusa, park; // 메두사와 공원의 좌표
    static int[] firstDr = {-1,1,0,0};
    static int[] firstDc = {0,0,-1,1};

    // 0 : 상, 1 : 우, 2 : 하, 3 : 좌, 4 : 오른쪽 위 대각선, 5 : 오른쪽 아래 대각선, 6 : 왼쪽 아래 대각선, 7 : 왼쪽 위 대각선
    static int[] eightDr = {-1,0,1,0,-1,1,1,-1};
    static int[] eightDc = {0,1,0,-1,1,1,-1,-1};

    static Deque<int[]> medusaWay;
    static int[][] medusaSight;


    static boolean isRange(int r,int c) {
        if(r < 0 || r>= N) return false;
        if(c < 0 || c>= N) return false;
        return true;
    }

    static boolean findMedusaWay(){

        // bfs로 최단경로 찾기 (역추적)
        int[][] copyMap = new int[N][]; // 역추적을 위한 map

        for(int i=0;i<N;i++){
            copyMap[i] = Arrays.copyOf(map[i],N);
            for(int j=0;j<N;j++){
                if(copyMap[i][j] == 1) copyMap[i][j] = -1;
            }
        }
        Deque<int[]> q = new ArrayDeque<>();
        int mr,mc;
        mr = medusa[0];
        mc = medusa[1];

        q.offer(new int[]{mr,mc,1});
        copyMap[mr][mc] = 1;


        while(!q.isEmpty()){
            int[] cur = q.pollFirst();
            int cr = cur[0];
            int cc = cur[1];
            int cnt = cur[2];

            if(cr == park[0] && cc == park[1]){ // 최종 목적지 까지 갔음
                break;
            }

            for(int d=0;d<4;d++){
                int nr = cr + firstDr[d];
                int nc = cc + firstDc[d];

                if(isRange(nr,nc) && copyMap[nr][nc] == 0){
                    copyMap[nr][nc] = cnt + 1;
                    q.offer(new int[]{nr,nc,cnt + 1});

                }
            }
        }


        if(copyMap[park[0]][park[1]]==0){ // 공원까지 갈 수 없는 경우
            return false;
        }

        /*
         * for(int i=0;i<N;i++) { for(int j=0;j<N;j++) {
         * System.out.printf("%2d",copyMap[i][j]); } System.out.println(); }
         */

        // 최단경로를 찾기 (cnt 값을 역추적)
        q = new ArrayDeque<>();
        q.offer(new int[]{park[0],park[1],copyMap[park[0]][park[1]]});
        medusaWay.offer(new int[]{park[0],park[1]});


        while(!q.isEmpty()){

            int[] cur = q.pollFirst();
            int cr = cur[0];
            int cc = cur[1];
            int cnt = cur[2];

            if(cnt == 1){
                medusaWay.pollFirst(); // 출발위치는 큐에서 삭제
                break;
            }

            // 우 좌 상 하
            // 현재 cnt 값 보다 1 작은 좌표 찾기
            for(int d=3;d>=0;d--){
                int nr = cr + firstDr[d];
                int nc = cc + firstDc[d];
                if( isRange(nr,nc) && copyMap[nr][nc] == cnt - 1){
                    q.offer(new int[]{nr,nc,cnt-1});
                    medusaWay.offerFirst(new int[]{nr,nc});
                    break;
                }
            }
        }



        return true;
    }



    static int findDirWithWarrior(int mr, int mc, int wr, int wc) {

        if(wr==mr) {
            if(wc<mc) return 3;
            if(wc>mc) return 1;
        }else if(wc==mc) {
            if(wr<mr) return 0;
            if(wr>mr) return 2;
        }

        if(wr<mr && wc<mc) {
            return 7;
        }
        if(wr<mr && wc>mc) {
            return 4;
        }

        if(wr>mr && wc<mc) {
            return 6;
        }

        if(wr>mr && wc>mc) {
            return 5;
        }

        return -1;
    }

    static void makeShadow(int r,int c,int md, int d,int[][] sight) { // (r,c) 좌표에서 d 방향으로 그림자(-1) 생김

        // 처음 (r,c) 좌표는 그림자에서 제외
        Deque<int[]> q = new ArrayDeque<>();
        q.offer(new int[] {r,c});

        while(!q.isEmpty()) {
            int size = q.size();

            int[] first_cur = q.peekFirst();

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

                int[] cur = q.pollFirst();
                int cr = cur[0];
                int cc = cur[1];

                int nr = cr + firstDr[md];
                int nc = cc + firstDc[md];

                if(isRange(nr,nc)) {
                    sight[nr][nc] = -1;
                    q.offer(new int[] {nr,nc});
                }else {
                    /*
                     * System.out.println("그림자 그린 결과"); for(int a=0;a<N;a++) { for(int b=0;b<N;b++)
                     * { System.out.printf("%2d", sight[a][b]); } System.out.println(); }
                     * System.out.println();
                     */
                    return;
                }
            }


            if(d > 3) {
                int nr,nc;
                nr = first_cur[0] + eightDr[d];
                nc = first_cur[1] + eightDc[d];

                if(isRange(nr,nc)) {
                    q.offerFirst(new int[] {nr,nc});
                    sight[nr][nc] = -1;
                }
            }


        }

    }

    static int checkSight(int r,int c,int d, int[][] medusaSight) { // (r,c) : 메두사의 좌표
        int cnt = 0;
        System.out.printf("%d 방향으로 바라봤을 때 \n",d);

        Deque<int[]> q = new ArrayDeque<>();
        q.offer(new int[] {r,c});

        int flag = 0;

        while(!q.isEmpty()) {
            int size = q.size();

            for(int i=0;i<size;i++) {
                int[] cur = q.pollFirst();
                int cr = cur[0];
                int cc = cur[1];
                if(warriorCnt[cr][cc] > 0 && medusaSight[cr][cc] == 1 ) {
                    System.out.printf("(%d, %d) 좌표 전사 %d개 돌로 변함 \n",cr,cc,warriorCnt[cr][cc]);
                    cnt += warriorCnt[cr][cc];
                    int dir = findDirWithWarrior(r,c,cr,cc);
                    makeShadow(cr,cc,d,dir,medusaSight);
                }

                int nr = cr + firstDr[d];
                int nc = cc + firstDc[d];

                if(!isRange(nr,nc)) {
                    flag = 1;
                    continue;
                }

                if(medusaSight[nr][nc]!=-1) {
                    medusaSight[nr][nc] = 1;
                }

                q.offer(new int[] {nr,nc});
            }
            if(flag==1) break;

            int nnr,nnc;
            int[] p = q.peekFirst();
            if(d==0 || d==1) { // 상 하
                nnr = p[0];
                nnc = p[1] - 1;
            }else { // 좌 우
                nnr = p[0] - 1;
                nnc = p[1];
            }

            if(isRange(nnr,nnc)) {
                q.offerFirst(new int[] {nnr,nnc});
                if(medusaSight[nnr][nnc]!=-1) medusaSight[nnr][nnc] = 1;
            }

            p = q.peekLast();
            if(d==0 || d==1) { // 상 하
                nnr = p[0];
                nnc = p[1] + 1;
            }else { // 좌 우
                nnr = p[0] + 1;
                nnc = p[1];
            }

            if(isRange(nnr,nnc)) {
                q.offerLast(new int[] {nnr,nnc});
                if(medusaSight[nnr][nnc]!=-1) medusaSight[nnr][nnc] = 1;
            }
        }


        return cnt;
    }

    static int findMedusaSight(int r,int c) {

        int  max = 0;
        int maxD = -1;

        for(int d=0;d<4;d++) {
            int[][] mSight = new int[N][N];

            int result = checkSight(r,c,d,mSight);

            if(result > max ) {
                max = result;
                maxD = d;
                medusaSight = mSight;
            }
        }

        System.out.println(maxD + "방향으로 결정");
        /*
         * for(int i=0;i<medusaSight.length;i++) {
         * System.out.println(Arrays.toString(medusaSight[i])); }
         * System.out.println("-----------------");
         */


        return max;

    }

    static int calcDistance(int r1,int c1, int r2, int c2) {
        return Math.abs(r1-r2) + Math.abs(c1-c2);
    }

    static int[] moveWarrior() {

        int moveCnt = 0, attackCnt = 0;

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

            int warriorR = warriors[i].r;
            int warriorC = warriors[i].c;

            if(warriorR==-1) continue;
            if(medusaSight[warriorR][warriorC]==1) continue;

            int distance = calcDistance(medusa[0],medusa[1],warriorR,warriorC);
            boolean isMoved = false;
            // first move
            for(int d=0;d<4;d++) {
                int warriorNr = warriorR + firstDr[d];
                int warriorNc = warriorC + firstDc[d];
                if(!isRange(warriorNr, warriorNc)) continue;
                if(medusaSight[warriorNr][warriorNc]==1) continue;

                if( distance > calcDistance(medusa[0],medusa[1],warriorNr,warriorNc)) {
                    warriorCnt[warriorR][warriorC] -= 1;

                    warriors[i].r = warriorNr;
                    warriors[i].c = warriorNc;

                    warriorCnt[warriorNr][warriorNc] += 1;
                    isMoved = true;
                    moveCnt += 1;
                    break;
                }
            }

            if(!isMoved) continue;

            if(warriors[i].r == medusa[0] && warriors[i].c == medusa[1]) { // 공격 그리고 죽음
                attackCnt += 1;
                warriorCnt[warriors[i].r][warriors[i].c] -= 1;
                warriors[i].r = -1;
                warriors[i].c = -1;
                continue; // 이 조건을 빠트림
            }


            warriorR = warriors[i].r;
            warriorC = warriors[i].c;

            distance = calcDistance(medusa[0],medusa[1],warriorR,warriorC);

            for(int d=0;d<4;d++) {
                int rd = (d+2)%4;
                int warriorNr = warriorR + firstDr[rd];
                int warriorNc = warriorC + firstDc[rd];
                if(!isRange(warriorNr, warriorNc)) continue;
                if(medusaSight[warriorNr][warriorNc]==1) continue;

                if( distance > calcDistance(medusa[0],medusa[1],warriorNr,warriorNc)) {
                    warriorCnt[warriorR][warriorC] -= 1;

                    warriors[i].r = warriorNr;
                    warriors[i].c = warriorNc;

                    warriorCnt[warriorNr][warriorNc] += 1;
                    moveCnt += 1;
                    break;
                }
            }

            if(warriors[i].r == medusa[0] && warriors[i].c == medusa[1]) {
                attackCnt += 1;
                warriorCnt[warriors[i].r][warriors[i].c] -= 1;
                warriors[i].r = -1;
                warriors[i].c = -1;
            }
        }

        return new int[] {moveCnt,attackCnt};
    }

    static void print(int[][] arr) {

        for(int i=0;i<arr.length;i++) {
            for(int j=0;j<arr[i].length;j++) {
                System.out.printf("%2d", arr[i][j]);
            }
            System.out.println();
        }
        System.out.println("------------------");
    }

    static void solve(){

        // 0. 메두사의 최단경로 찾기 (medusaWay 큐에 기록)
        if(!findMedusaWay()) {
            System.out.println(-1);
            return;
        }

        StringBuilder sb = new StringBuilder();

        while(true) {
            // 1. 메두사 이동
            int[] way = medusaWay.pollFirst();
            int nr = way[0];
            int nc = way[1];
            medusa[0] = nr;
            medusa[1] = nc;

            System.out.printf("메두사 위치 : (%d, %d) \n",medusa[0],medusa[1]);

            if(medusa[0]==park[0] && medusa[1] == park[1]) {
                sb.append(0);
                break;
            }

            for(int m=0;m<M;m++) {
                Warrior warrior = warriors[m];
                if(warrior.r == -1) continue; // 이 조건도 빠트림

                if(warrior.r == medusa[0] && warrior.c == medusa[1]) {
                    warriorCnt[warrior.r][warrior.c] -= 1;
                    warrior.r = -1;
                    warrior.c = -1;

                    System.out.printf("%d 번 전사 이동한 메두사에게 잡힘\n",m);
                }
            }

            System.out.println("warriorCnt[][]");
            print(warriorCnt);


            // 2. 메두사 시선
            int stoneCnt = findMedusaSight(medusa[0],medusa[1]);

            System.out.println("메두사 시선");
            print(medusaSight);
            System.out.printf("돌이 된 전사의 수 : %d \n", stoneCnt);


            // 3. 전사들 이동
            int[] warriorMoveResult = moveWarrior();

            System.out.println("전사들의 이동 후 결과");
            print(warriorCnt);

            sb.append(warriorMoveResult[0]).append(" ").append(stoneCnt).append(" ").append(warriorMoveResult[1]).append("\n");
        }

        System.out.println(sb.toString());

    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        Deque<Integer> dq = new ArrayDeque<>();


        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new int[N][N];
        warriors = new Warrior[M];
        warriorCnt = new int[N][N];
        medusa = new int[2];
        park = new int[2];

        st = new StringTokenizer(br.readLine());
        medusa[0] = Integer.parseInt(st.nextToken());
        medusa[1] = Integer.parseInt(st.nextToken());
        park[0] = Integer.parseInt(st.nextToken());
        park[1] = Integer.parseInt(st.nextToken());
        medusaWay = new ArrayDeque<>();


        st = new StringTokenizer(br.readLine());
        for(int i=0;i<M;i++){
            int r,c;
            r = Integer.parseInt(st.nextToken());
            c = Integer.parseInt(st.nextToken());
            warriors[i] = new Warrior(r,c);
            warriorCnt[r][c] += 1;
        }

        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<N;j++){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        solve();

    }
}