Chương trình C ++ để tìm người chiến thắng trong trò chơi tô màu ô

Giả sử chúng ta có hai mảng A và B đều có N phần tử mỗi mảng. Hãy xem xét Amal và Bimal đang chơi trò chơi trên bảng có số ô được đánh số từ 1 đến N. Và N-1 đường. Đường đang nối hai ô. Vì vậy, con đường thứ i là nối A [i] đến B [i]. Mọi ô có thể được tiếp cận từ mọi ô khác bằng cách di chuyển liên tục sang ô liền kề. Ban đầu ô 1 được đánh dấu là màu đen và ô N là màu trắng. Các ô khác không được tô màu. Amal chơi trước, và họ chơi xen kẽ. Amal chọn một ô chưa được tô màu liền kề với ô màu đen và sơn màu đen. Bimal chọn một ô chưa được tô màu liền kề với ô màu trắng và sơn màu trắng. Khi một người chơi không thể vẽ một ô, anh ta sẽ thua cuộc. Chúng ta phải tìm ra người chiến thắng.

Vì vậy, nếu đầu vào là A =[3, 1, 3, 7, 5, 1]; B =[6, 2, 1, 4, 7, 4], thì kết quả đầu ra sẽ là Amal, vì nếu Amal đầu tiên tô ô 2 màu đen, anh ta sẽ thắng bất kể Bimal di chuyển như thế nào.

Các bước

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

 N:=99999Xác định một danh sách kề adjListXác định ba mảng lớn p, d và sszXác định một hàm dfs (), điều này sẽ lấy nd, par, dep, p [nd]:=par d [nd]:=dep ssz [nd]:=1 cho mỗi nút i trong adjList [nd], thực hiện nếu mệnh XOR của tôi khác 0, thì:dfs (i, nd, dep + 1) ssz [nd]:=ssz [nd] + ssz [i] Từ phương thức chính, thực hiện như sau:n:=size của Afor khởi tạo i:=1, khi i  =n, sau đó là "Bimal", nếu không "Amal"  
 Ví dụ 
 

 Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn - 
 
 #include  using namespace std; int N =99999; vector > adjList (N); vector  p (N), d (N), ssz (N ); void dfs (int nd, int par, int dep) {p [nd] =par; d [nd] =dep; ssz [nd] =1; for (int i:adjList [nd]) {if (i ^ par) {dfs (i, nd, dep + 1); ssz [nd] + =ssz [i]; }}} string Giải quyết (vector  A, vector  B) {int n =A.size (); for (int i =1; i  =n? "Bimal":"Amal");} int main () {vector  A ={3, 1, 3, 7, 5, 1}; vectơ  B ={6, 2, 1, 4, 7, 4}; cout < 
 Đầu vào 
 
 {3, 1, 3, 7, 5, 1}, {6, 2, 1, 4, 7, 4} 
 
 Đầu ra 
 
 Amal