Hỏi bài tập đếm số ô an toàn trong bảng

#1

Xét ví dụ sau:
Ở ví dụ trên ta có: n = 5 (Vì có 5 pháo đài)

row = [0,1,1,2,5]
col = [0,1,3,3,6]

Tức là trong 5 pháo đài:

  • 1 Pháo đài nằm ở hàng 0, cột 0
  • 1 Pháo đài nằm ở hàng 1, cột 1
  • 1 Pháo đài nằm ở hàng 1, cột 3
  • 1 Pháo đài nằm ở hàng 2, cột 3
  • 1 Pháo đài nằm ở hàng 5, cột 6

Mỗi pháo đài có thể bắn theo 4 hướng, các vị trí được tô màu đỏ là vùng nguy hiểm do nằm trong tầm bắn của các pháo đài. Các ô màu xanh là các vùng an toàn, nhiệm vụ của ta là đếm số ô màu xanh này.

Vậy kết quả xuất ra màn hình: 16

mọi người cho mình xin giải thuật bài này

image.png841×364 10.8 KB

#3

Theo mình cái này hơi giống thuật toán trò Minesweeper. Bạn có thể xem video làm trò chơi đấy của họ trên youtube! Rồi follow nó làm tương tự

3 Likes
#4 
n = int(input())
row = []
col = []
for i in range(n):
   row.append(int(input('nhap hang: ')))
   col.append(int(input('nhap cot: ')))
count_row=1
count_col=1
for i in range(n-1):
	if row[i]!=row[i+1]:
		count_row+=1
	if col[i]!=col[i+1]:
		count_col+=1
print(count_col)

print("\n",count_row)
print(int((8-count_row)*(8-count_col)))

mình có tham khảo code nhưng vẫn chưa hiểu lắm :smile: không biết tại sao như thế nữa

#5

xem video này nhé bạn!

4 Likes
#6

Mỗi pháo đài sẽ khống chế một cột và một dòng, mà hình chữ nhật bỏ đi cột hay dòng thì vẫn là hình chữ nhật :smiley: nên như này thì đúng hơn.

# ruby

def count_cleared_cells(no_row, no_col, *cannons)
   cannons.reject! {|c| c.x >= no_row || c.y >= no_col} # có thể bỏ qua dòng này.
   occ_xs = cannons.uniq &:x 
   occ_ys = cannons.uniq &:y
   (no_row - occ_xs.length) * (no_col - occ_ys.length)
end

Code trên cho dữ liệu xoắn chút là toi.

Hai mảng trên ứng với occ_xs và occ_ys.

2 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?