Xin hướng làm bài trò chơi đuổi bắt

[coderchamchi (coderbee)]

Kiên, Trung và Hà đang chơi trò đuổi bắt, Trung và Hà là người đuổi và Kiên là người chạy.

Luật chơi của game như sau, có n ô vuông được đánh số lần lượt từ 1 đến n , các ô vuông có thể ở các vị trí riêng biệt hoặc được kết nối với nhau. Sự kết nối giữa các ô vuông được biểu diễn bằng matrix connections trong đó mỗi phần tử con của matrix là một mảng gồm hai phần tử có dạng [i, j] biểu diễn ô số i được kết nối với ô số j .
Ban đầu Trung và Hà đang đứng ở hai vị trí được biểu diễn bằng mảng locations và Kiên đang đứng ở vị trí x nào đó. Trò chơi được diễn ra theo kiểu thay lượt chơi vòng tròn, Kiên đi đầu tiên rồi đến lượt Trung rồi đến lượt Hà. Mỗi lượt người chơi có thể đứng nguyên tại vị trí hiện tại hoặc di chuyển sang ô kế bên (những ô được kết nối với ô hiện tại), trò chơi kết thúc khi Kiên bị bắt (vị trí của Kiên trùng với vị trí của Trung hoặc Hà). Nhiệm vụ của bạn là tìm số lượng ô ban đầu mà Kiên có thể chọn để chắc chắn Kiên sẽ không bao giờ bị bắt, giả sử tất cả người chơi đều chơi một cách tối ưu.

Ví dụ:

• Với n = 3 , connections = [] và locations = [1,2] thì đầu ra của safeCells(n, connections, locations) = 1 .
  Ban đầu, Trung và Hà đang ở vị trí số 1 và số 2 , Kiên chỉ có một sự lựa chọn duy nhất là bắt đầu ở ô số 3 để không bị bắt (vì tất ô đều không được kết nối với nhau nên sẽ không có cách nào để đi từ ô số 1 hoặc số 2 sang ô số 3).
• Với n = 3, connections = [[2,3]] và locations = [2,3] thì đầu ra của safeCells(n, connections, locations) = 1 .
  Ban đầu, Trung và Hà đang ở vị trí số 2 và số 3 . Kiên chỉ có một sự lựa chọn duy nhất là bắt đầu ở ô số 1 để không bị bắt (vì ô số 2 và ô số 3 được kết nối với nhau nên Trung và Hà chỉ có thể đi từ ô số 2 sang ô số 3 và ngược lại).