그리드에서 보호되지 않은 셀 수 계산

2257. 그리드에서 보호되지 않은 셀 개수

난이도:중

주제: 어레이, 매트릭스, 시뮬레이션

0 인덱스 m x n 그리드를 나타내는 두 개의 정수 m과 n이 제공됩니다. 또한 Guards[i] = [row_i, col_i] 및 wall[j] = [row_{j, col}j_{]는 i}번째 ^{가드의 위치를 ​​나타내며, j}번째 ^{벽입니다.}

경비원은 벽이나 다른 경비원이

방해하지 않는 한 자신의 위치에서 시작하여 기본 네 방향(동서남북)의 모든 감방을 볼 수 있습니다. 셀을 볼 수 있는 경비원이 적어도 한 명 있으면 셀은 보호됩니다.

보호되지 않은 비어 있는 셀의 수를 반환합니다.

예 1:

• 입력: m = 4, n = 6, 경비원 = [[0,0],[1,1],[2,3]], 벽 = [[0,1],[2, 2],[1,4]]
• 출력: 7
• 설명: 위 다이어그램에서 보호된 셀과 보호되지 않은 셀은 각각 빨간색과 녹색으로 표시됩니다.
  보호되지 않은 셀이 총 7개이므로 7개를 반환합니다.

예 2:

• 입력: m = 3, n = 3, 경비원 = [[1,1]], 벽 = [[0,1],[1,0],[2,1],[1, 2]]
• 출력: 4
• 설명: 위 다이어그램에서 보호되지 않은 셀은 녹색으로 표시됩니다.
  보호되지 않은 셀이 총 4개이므로 4개를 반환합니다.

제약조건:

1 5 2 5 1 <=guards.length, wall.length <= 5 * 10
• 4
2 <= Guards.length wall.length <= m * n
경비대[i].length == 벽[j].length == 2
0 <= 행
• i_{, 행}j _{< 음}
0 <= col
• i_{, col}j _{< ㄴ}
경비원과 성벽의 모든 위치는
• 독특합니다.

힌트:

그리드를 나타내는 2D 배열을 만듭니다. 경비원이 볼 수 있는 타일을 표시해 주실 수 있나요?
경비원을 반복하고 4개 방향 각각에 대해 현재 타일을 전진시키고 타일을 표시합니다. 언제 발전을 멈춰야 할까요?

해결책:

적어도 한 명의 경비원이 지키고 있는 셀을 표시해야 합니다. 경비병들은 기본 네 방향(북, 남, 동, 서)을 볼 수 있지만 벽으로 인해 시야가 차단됩니다. 이 프로세스를 시뮬레이션하고 보호되지 않은 셀 수를 계산할 수 있습니다.

접근하다:

1. 그리드 만들기: 그리드를 2D 배열로 표현할 수 있으며 각 셀은 벽, 가드 또는 비어 있을 수 있습니다.
2. 보호된 셀 표시: 각 가드에 대해 네 방향(북, 남쪽, 동쪽, 서쪽)으로 반복하고 볼 수 있는 모든 셀을 표시하고 벽이나 다른 가드를 만나면 중지합니다.
3. 보호되지 않은 셀 개수: 보호된 셀을 표시한 후 보호되지 않고 벽이 아닌 셀이 몇 개 있는지 세어보세요.

단계:

1. 그리드 초기화: 그리드를 나타내는 2D 배열을 만듭니다. 반복하면서 벽, 경비원, 보호 구역으로 셀을 표시합니다.

2. 경비 범위 시뮬레이션:

   • 경비원은 4방향(동서남북)을 볼 수 있습니다.
   • 벽이나 다른 경비원을 만날 때까지 각 경비원이 지키고 있는 세포를 표시하세요.

3. 보호되지 않은 셀 계산: 모든 가드를 처리한 후 벽, 가드, 보호되지 않은 셀을 계산합니다.

이 솔루션을 PHP로 구현해 보겠습니다: 2257. 그리드에서 보호되지 않은 셀 개수

  
  
  설명:





초기화:


빈 셀의 경우 그리드가 0으로 초기화됩니다. 벽과 가드에는 고유한 상수가 표시되어 있습니다.



가드 시뮬레이션:


각 가드에 대해 네 방향 모두의 움직임을 시뮬레이션하여 벽이나 다른 가드에 부딪힐 때까지 셀을 보호된 것으로 표시합니다.



보호되지 않은 셀 계산:

모든 가드를 처리한 후 그리드를 반복하고 여전히 0으로 표시된 셀을 계산합니다.





  
  
  성능:



시간 복잡도: O(m x n g x d), 여기서 g는 경비원 수이고 d입니다. 은 각 경비병이 이동할 수 있는 방향의 셀 수입니다. 여행.
공간 복잡도: 그리드의 경우 O(m x n)




  
  
  시간 복잡도:




그리드 초기화: _O(m * n), 여기서 _m 및 n는 그리드의 크기입니다.

마킹 가드 시야: 각 가드는 네 방향에서 최대 행이나 열의 길이를 확인합니다. 따라서 각 경비병은 O(m n)입니다.

보호되지 않은 셀 계산: O(m * n).


따라서 전체 복잡도는 O(m * n)이며, 이는 문제 제약 조건을 고려할 때 효율적입니다.


  
  
  엣지 케이스:



가드나 벽이 없으면 전체 그리드가 보호되지 않습니다.
모든 셀이 보호되거나 벽인 경우 결과는 보호되지 않은 셀이 0개입니다.


연락처 링크

이 시리즈가 도움이 되었다면 GitHub에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!

이렇게 더 유용한 콘텐츠를 원하시면 저를 팔로우해주세요.


링크드인
깃허브



          

            
  

            
        
위 내용은 그리드에서 보호되지 않은 셀 수 계산의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!