may_be_cleaning_robot

 avatar
SSkyFire
java
2 months ago
17 kB
4
Indexable
Never
Robot dọn dẹp
Chúng ta phải vạch đường đi cho robot dọn dẹp làm sạch sàn phòng hình chữ nhật có kích thước NxM. 
Sàn phòng được lát gạch vuông có kích thước vừa với robot dọn dẹp (1×1). 
Có gạch sạch và gạch bẩn , và robot có thể thay đổi gạch bẩn thành gạch sạch bằng cách truy cập vào gạch. 
Ngoài ra có thể có một số chướng ngại vật (đồ nội thất) có kích thước vừa với một viên gạch trong phòng. 
Nếu có chướng ngại vật trên ô, robot không thể ghé thăm nó. Robot di chuyển đến ô liền kề chỉ bằng một lần di chuyển. 
Ô mà robot di chuyển lên phải là một trong bốn ô (tức là đông, tây, bắc hoặc nam) liền kề với ô có robot hiện diện. 
Robot có thể ghé thăm một ô hai lần trở lên.
Nhiệm vụ của bạn là viết một chương trình tính toán số lần di chuyển tối thiểu để robot có thể thay đổi tất cả các ô bẩn thành các ô sạch, nếu có thể.
Ví dụ :
Sau đây là một căn phòng có kích thước 5x7, có 3 viên gạch bẩn và 0 đồ đạc. Câu trả lời cho trường hợp này là 8.
Đầu vào
Dữ liệu vào bao gồm nhiều bản đồ, dòng đầu tiên là số lượng test case T (T <= 50).
Mỗi trường hợp thử nghiệm bắt đầu bằng N và M đại diện cho kích thước của căn phòng. ( 5 == N, M <= 100)
Dòng N tiếp theo thể hiện sự sắp xếp của căn phòng với nội dung mô tả như sau:

0 : viên gạch sạch
1 : viên gạch bẩn
2 : một món đồ nội thất (chướng ngại vật)
3 : robot (vị trí ban đầu)

Trong bản đồ số ô bẩn không vượt quá 10 và chỉ có một robot .
đầu ra
In mỗi test case trên hai dòng, dòng đầu tiên của mỗi test case là "Case #x", trong đó x là số test case. 
Dòng tiếp theo là số lần di chuyển tối thiểu để robot có thể thay đổi tất cả các ô bẩn thành các ô sạch. 
Nếu bản đồ có các ô bẩn mà rô-bốt không thể tiếp cận thì chương trình của bạn sẽ xuất ra -1.
input1//
Sample

Input

5

5 7

0 0 0 0 0 0 0

0 3 0 0 0 1 0

0 0 0 0 0 0 0

0 1 0 0 0 1 0

0 0 0 0 0 0 0

5 15

0 0 0 0 2 0 2 0 0 0 0 1 2 0 1

0 0 0 1 0 2 0 2 2 0 1 2 0 0 0

2 1 0 2 0 1 0 2 0 0 0 0 0 0 0

0 0 0 1 0 2 0 0 1 2 0 0 2 0 0

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

...............

Output

Case #1

8

Case #2

38


//input he thong
5
5 15
0 0 0 0 2 0 2 0 0 0 0 1 2 0 1 
0 0 0 1 0 2 0 2 2 0 1 2 0 0 0 
2 1 0 2 0 1 0 2 0 0 0 0 0 0 0 
0 0 0 1 0 2 0 0 1 2 0 0 2 0 0 
0 2 1 0 2 0 0 0 0 0 3 0 0 0 0 
9 15
2 0 2 2 0 2 0 0 2 0 0 0 0 0 2 
0 2 2 2 0 0 0 0 0 2 0 1 0 0 2 
2 0 0 1 2 0 3 0 1 0 0 0 0 2 0 
2 0 0 2 2 0 0 0 0 0 0 0 0 0 0 
0 2 0 0 0 0 0 0 0 0 0 0 2 0 1 
2 0 0 0 0 0 0 0 2 0 2 0 0 0 0 
0 0 2 2 0 0 0 0 0 0 0 0 0 2 0 
0 0 0 2 0 0 0 0 2 0 0 0 1 0 0 
2 0 0 0 2 0 1 2 2 0 0 0 0 0 2 
14 32
0 0 0 2 0 1 0 2 2 0 0 0 0 0 0 0 2 0 0 0 0 0 2 0 0 0 2 0 2 0 2 2 
0 0 0 0 0 0 0 0 2 2 2 2 0 2 0 0 0 0 0 2 2 0 2 0 0 2 0 0 0 0 0 0 
0 0 2 0 0 0 2 2 2 0 0 0 0 2 0 0 0 3 0 0 2 0 2 0 0 2 0 0 0 0 0 2 
0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 2 0 0 1 0 0 0 2 0 0 0 0 0 0 2 0 
0 0 2 1 0 0 0 0 0 0 2 2 0 0 0 0 0 0 0 2 0 0 0 0 0 0 2 0 0 0 2 0 
0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 2 0 0 0 0 2 0 2 0 0 0 0 0 0 0 2 
0 2 0 0 0 0 0 0 0 2 0 0 2 0 0 2 0 2 0 0 0 0 0 0 0 2 0 0 0 2 2 0 
0 0 0 0 0 2 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 2 0 0 
0 2 2 0 0 0 0 0 2 0 0 2 2 0 0 2 0 0 2 2 0 0 2 0 2 0 0 0 2 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 2 0 0 0 2 2 0 2 2 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 2 0 2 0 0 
2 2 2 0 0 0 0 0 2 0 2 2 2 0 0 0 2 0 0 0 2 0 0 0 0 0 2 0 0 0 0 2 
0 2 0 0 0 2 0 0 0 2 0 0 1 0 0 2 0 0 0 1 0 0 0 0 0 2 0 0 0 0 0 0 
0 2 2 0 0 2 0 0 2 0 2 1 0 2 0 0 1 0 0 0 2 2 0 0 0 2 2 2 0 0 2 0 
14 42
0 2 0 0 0 0 0 0 0 2 2 2 0 2 0 2 0 0 2 0 2 0 0 2 0 0 0 0 0 0 0 0 3 0 2 0 2 0 0 0 0 2 
0 0 0 0 0 2 2 2 0 0 0 2 0 2 0 0 0 0 0 2 0 2 0 0 0 1 0 2 1 2 0 0 0 0 0 0 0 0 0 2 2 1 
0 0 0 1 0 2 0 2 0 0 0 0 2 0 0 0 0 0 0 0 2 0 0 0 2 2 0 0 0 0 2 2 1 0 0 2 0 0 0 2 0 2 
0 0 2 0 0 0 2 0 0 2 0 0 0 2 0 0 0 0 0 0 0 2 2 2 0 0 0 0 0 2 0 0 0 0 0 2 2 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 2 2 0 0 0 0 0 0 2 0 0 0 0 0 2 0 0 0 0 2 0 0 2 0 0 0 2 0 0 0 0 
2 0 0 0 0 0 0 0 0 0 2 0 2 0 0 0 0 0 2 2 2 0 0 0 0 0 0 0 0 2 2 0 0 0 2 2 0 0 2 0 0 0 
0 0 0 0 0 2 0 2 0 2 0 0 0 0 0 0 0 2 0 0 0 0 0 1 0 0 0 0 0 0 2 0 0 0 0 2 2 2 0 0 0 0 
0 0 0 2 0 0 0 0 0 0 0 0 2 2 0 0 0 2 0 0 0 0 0 2 0 0 0 0 2 0 0 0 0 0 0 0 0 2 0 0 0 2 
0 0 0 2 0 0 0 2 1 2 0 0 0 0 2 0 0 0 0 0 0 0 0 0 2 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 2 
0 0 0 2 1 0 0 0 0 0 0 0 0 0 0 0 0 2 2 0 2 2 0 2 2 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 2 0 0 0 0 2 0 0 0 2 2 2 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 2 2 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 2 2 0 0 0 0 0 0 0 0 2 0 2 0 0 2 0 0 0 0 0 
2 0 0 0 0 0 0 0 0 2 0 0 0 0 2 0 0 0 2 0 0 2 0 2 2 0 2 0 0 2 0 2 2 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 1 0 0 2 2 2 2 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 2 2 0 0 0 2 0 0 
16 22
0 2 0 0 0 1 2 0 0 0 1 2 0 0 2 0 2 0 2 0 2 0 
0 0 0 0 0 0 0 0 2 0 2 0 2 0 0 0 0 2 0 0 0 2 
1 0 0 2 0 2 0 2 2 0 0 0 0 0 0 2 0 0 2 0 0 2 
2 0 0 0 0 0 2 2 0 0 0 2 0 0 0 0 0 2 0 0 0 0 
0 0 0 0 0 0 2 0 0 0 0 0 0 0 2 2 2 0 2 2 0 0 
2 0 0 0 2 2 2 0 0 2 0 2 0 0 2 0 2 0 0 0 0 2 
2 0 2 0 0 0 0 0 0 2 0 0 0 0 0 2 2 0 0 0 2 0 
2 0 0 2 2 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 
2 0 0 2 0 2 0 2 0 0 2 2 0 2 0 2 0 0 0 0 0 2 
0 0 0 2 0 0 2 0 0 0 0 0 0 0 2 0 0 0 2 0 0 2 
2 2 0 0 2 0 2 1 0 3 0 0 1 2 0 0 0 2 0 1 0 0 
0 0 0 2 0 2 0 0 0 0 2 2 0 2 2 0 0 0 0 0 0 1 
2 2 0 0 2 0 2 0 0 2 0 0 2 2 1 0 2 0 0 0 2 0 
0 0 0 0 0 0 2 0 2 2 2 0 0 0 0 0 0 0 2 2 2 2 
2 2 0 2 0 0 0 2 0 1 0 0 0 2 0 2 0 0 0 0 0 0 
0 0 0 2 0 2 2 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 

Case #1
38
Case #2
37
Case #3
52
Case #4
-1
Case #5
78

//solution
Robot dọn dẹp
Chúng ta phải vạch đường đi cho robot dọn dẹp làm sạch sàn phòng hình chữ nhật có kích thước NxM. 
Sàn phòng được lát gạch vuông có kích thước vừa với robot dọn dẹp (1×1). 
Có gạch sạch và gạch bẩn , và robot có thể thay đổi gạch bẩn thành gạch sạch bằng cách truy cập vào gạch. 
Ngoài ra có thể có một số chướng ngại vật (đồ nội thất) có kích thước vừa với một viên gạch trong phòng. 
Nếu có chướng ngại vật trên ô, robot không thể ghé thăm nó. Robot di chuyển đến ô liền kề chỉ bằng một lần di chuyển. 
Ô mà robot di chuyển lên phải là một trong bốn ô (tức là đông, tây, bắc hoặc nam) liền kề với ô có robot hiện diện. 
Robot có thể ghé thăm một ô hai lần trở lên.
Nhiệm vụ của bạn là viết một chương trình tính toán số lần di chuyển tối thiểu để robot có thể thay đổi tất cả các ô bẩn thành các ô sạch, nếu có thể.
Ví dụ :
Sau đây là một căn phòng có kích thước 5x7, có 3 viên gạch bẩn và 0 đồ đạc. Câu trả lời cho trường hợp này là 8.
Đầu vào
Dữ liệu vào bao gồm nhiều bản đồ, dòng đầu tiên là số lượng test case T (T <= 50).
Mỗi trường hợp thử nghiệm bắt đầu bằng N và M đại diện cho kích thước của căn phòng. ( 5 == N, M <= 100)
Dòng N tiếp theo thể hiện sự sắp xếp của căn phòng với nội dung mô tả như sau:

0 : viên gạch sạch
1 : viên gạch bẩn
2 : một món đồ nội thất (chướng ngại vật)
3 : robot (vị trí ban đầu)

Trong bản đồ số ô bẩn không vượt quá 10 và chỉ có một robot .
đầu ra
In mỗi test case trên hai dòng, dòng đầu tiên của mỗi test case là "Case #x", trong đó x là số test case. 
Dòng tiếp theo là số lần di chuyển tối thiểu để robot có thể thay đổi tất cả các ô bẩn thành các ô sạch. 
Nếu bản đồ có các ô bẩn mà rô-bốt không thể tiếp cận thì chương trình của bạn sẽ xuất ra -1.

5
5 15
0 0 0 0 2 0 2 0 0 0 0 1 2 0 1 
0 0 0 1 0 2 0 2 2 0 1 2 0 0 0 
2 1 0 2 0 1 0 2 0 0 0 0 0 0 0 
0 0 0 1 0 2 0 0 1 2 0 0 2 0 0 
0 2 1 0 2 0 0 0 0 0 3 0 0 0 0 
9 15
2 0 2 2 0 2 0 0 2 0 0 0 0 0 2 
0 2 2 2 0 0 0 0 0 2 0 1 0 0 2 
2 0 0 1 2 0 3 0 1 0 0 0 0 2 0 
2 0 0 2 2 0 0 0 0 0 0 0 0 0 0 
0 2 0 0 0 0 0 0 0 0 0 0 2 0 1 
2 0 0 0 0 0 0 0 2 0 2 0 0 0 0 
0 0 2 2 0 0 0 0 0 0 0 0 0 2 0 
0 0 0 2 0 0 0 0 2 0 0 0 1 0 0 
2 0 0 0 2 0 1 2 2 0 0 0 0 0 2 
14 32
0 0 0 2 0 1 0 2 2 0 0 0 0 0 0 0 2 0 0 0 0 0 2 0 0 0 2 0 2 0 2 2 
0 0 0 0 0 0 0 0 2 2 2 2 0 2 0 0 0 0 0 2 2 0 2 0 0 2 0 0 0 0 0 0 
0 0 2 0 0 0 2 2 2 0 0 0 0 2 0 0 0 3 0 0 2 0 2 0 0 2 0 0 0 0 0 2 
0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 2 0 0 1 0 0 0 2 0 0 0 0 0 0 2 0 
0 0 2 1 0 0 0 0 0 0 2 2 0 0 0 0 0 0 0 2 0 0 0 0 0 0 2 0 0 0 2 0 
0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 2 0 0 0 0 2 0 2 0 0 0 0 0 0 0 2 
0 2 0 0 0 0 0 0 0 2 0 0 2 0 0 2 0 2 0 0 0 0 0 0 0 2 0 0 0 2 2 0 
0 0 0 0 0 2 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 2 0 0 
0 2 2 0 0 0 0 0 2 0 0 2 2 0 0 2 0 0 2 2 0 0 2 0 2 0 0 0 2 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 2 0 0 0 2 2 0 2 2 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 2 0 2 0 0 
2 2 2 0 0 0 0 0 2 0 2 2 2 0 0 0 2 0 0 0 2 0 0 0 0 0 2 0 0 0 0 2 
0 2 0 0 0 2 0 0 0 2 0 0 1 0 0 2 0 0 0 1 0 0 0 0 0 2 0 0 0 0 0 0 
0 2 2 0 0 2 0 0 2 0 2 1 0 2 0 0 1 0 0 0 2 2 0 0 0 2 2 2 0 0 2 0 
14 42
0 2 0 0 0 0 0 0 0 2 2 2 0 2 0 2 0 0 2 0 2 0 0 2 0 0 0 0 0 0 0 0 3 0 2 0 2 0 0 0 0 2 
0 0 0 0 0 2 2 2 0 0 0 2 0 2 0 0 0 0 0 2 0 2 0 0 0 1 0 2 1 2 0 0 0 0 0 0 0 0 0 2 2 1 
0 0 0 1 0 2 0 2 0 0 0 0 2 0 0 0 0 0 0 0 2 0 0 0 2 2 0 0 0 0 2 2 1 0 0 2 0 0 0 2 0 2 
0 0 2 0 0 0 2 0 0 2 0 0 0 2 0 0 0 0 0 0 0 2 2 2 0 0 0 0 0 2 0 0 0 0 0 2 2 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 2 2 0 0 0 0 0 0 2 0 0 0 0 0 2 0 0 0 0 2 0 0 2 0 0 0 2 0 0 0 0 
2 0 0 0 0 0 0 0 0 0 2 0 2 0 0 0 0 0 2 2 2 0 0 0 0 0 0 0 0 2 2 0 0 0 2 2 0 0 2 0 0 0 
0 0 0 0 0 2 0 2 0 2 0 0 0 0 0 0 0 2 0 0 0 0 0 1 0 0 0 0 0 0 2 0 0 0 0 2 2 2 0 0 0 0 
0 0 0 2 0 0 0 0 0 0 0 0 2 2 0 0 0 2 0 0 0 0 0 2 0 0 0 0 2 0 0 0 0 0 0 0 0 2 0 0 0 2 
0 0 0 2 0 0 0 2 1 2 0 0 0 0 2 0 0 0 0 0 0 0 0 0 2 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 2 
0 0 0 2 1 0 0 0 0 0 0 0 0 0 0 0 0 2 2 0 2 2 0 2 2 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 2 0 0 0 0 2 0 0 0 2 2 2 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 2 2 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 2 2 0 0 0 0 0 0 0 0 2 0 2 0 0 2 0 0 0 0 0 
2 0 0 0 0 0 0 0 0 2 0 0 0 0 2 0 0 0 2 0 0 2 0 2 2 0 2 0 0 2 0 2 2 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 1 0 0 2 2 2 2 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 2 2 0 0 0 2 0 0 
16 22
0 2 0 0 0 1 2 0 0 0 1 2 0 0 2 0 2 0 2 0 2 0 
0 0 0 0 0 0 0 0 2 0 2 0 2 0 0 0 0 2 0 0 0 2 
1 0 0 2 0 2 0 2 2 0 0 0 0 0 0 2 0 0 2 0 0 2 
2 0 0 0 0 0 2 2 0 0 0 2 0 0 0 0 0 2 0 0 0 0 
0 0 0 0 0 0 2 0 0 0 0 0 0 0 2 2 2 0 2 2 0 0 
2 0 0 0 2 2 2 0 0 2 0 2 0 0 2 0 2 0 0 0 0 2 
2 0 2 0 0 0 0 0 0 2 0 0 0 0 0 2 2 0 0 0 2 0 
2 0 0 2 2 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 
2 0 0 2 0 2 0 2 0 0 2 2 0 2 0 2 0 0 0 0 0 2 
0 0 0 2 0 0 2 0 0 0 0 0 0 0 2 0 0 0 2 0 0 2 
2 2 0 0 2 0 2 1 0 3 0 0 1 2 0 0 0 2 0 1 0 0 
0 0 0 2 0 2 0 0 0 0 2 2 0 2 2 0 0 0 0 0 0 1 
2 2 0 0 2 0 2 0 0 2 0 0 2 2 1 0 2 0 0 0 2 0 
0 0 0 0 0 0 2 0 2 2 2 0 0 0 0 0 0 0 2 2 2 2 
2 2 0 2 0 0 0 2 0 1 0 0 0 2 0 2 0 0 0 0 0 0 
0 0 0 2 0 2 2 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 

Case #1
38
Case #2
37
Case #3
52
Case #4
-1
Case #5
78



package cleaning_robot;

import java.io.FileInputStream;
import java.util.Scanner;


public class Solution_rb_ver2 {
	
	static class Queue{
		static int maxq = 100001 ;
		int data[] = new int[maxq] ;
		int front, rear ;
		
		Queue(){
			front = rear = -1; 
		}
		void reset(){
			front = rear = -1; 
		}
		boolean isEmpty(){
			return front == rear ;
		}
		void enQueue(int v){
			data[++rear] = v ;
		}
		int deQueue(){
			return data[++front] ;
		}
		int peek(){
			return data[front+1] ;
		}
		
	}
	
	
	static int N, M, startX, startY, minCanTim, demVetBan; 
	static int[][] map; // luu input
	static int[][] pos; // vi tri vet ban 
	static int[][] visitBFS;
	static int[] visitBackTrack;// lan va dem kc
	static int[][] maTranKe;
	static long startFunc, endFunc;
	static Queue qx = new Queue();
	static Queue qy = new Queue();
	static boolean checkClean;

//	static int[] r_spin = { 0, 0, -1, 1 };
//	static int[] c_spin = { -1, 1, 0, 0 };
	static int[] dx = { 0, 0,-1, 1} ;
	static int[] dy = {-1, 1, 0, 0} ;
	
	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("src/cleaning_robot/input_clean_robot.txt"));
		Scanner sc = new Scanner(System.in);

		int T = sc.nextInt();
		//startFunc = System.currentTimeMillis();
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();
			M = sc.nextInt();

//			map = new int[N][M];
//			pos = new int[N * M + 1][2]; // toi da 10 vet ban 
//			visit = new int[N][M];
//			countDirty = 1;
			map = new int[N][M] ;
			pos = new int[12][2] ;
			visitBFS = new int[N][M] ;
			demVetBan = 1; 
			
			for (int i = 0; i < N ; i++) {
				for (int j = 0; j < M ; j++) {
					map[i][j] = sc.nextInt();
					if( map[i][j] == 3){//lay vi tri robot dau tien coi la vet ban
						pos[0][0] = i ;
						pos[0][1] = j ;
					}
					if( map[i][j] == 1){
						pos[demVetBan][0] = i ;
						pos[demVetBan][1] = j ;
						demVetBan++ ;
					}
					
				}
			}
			
			//BFS lan tu robot den vet ban
			
//			int ans = BFS(1, 1, 3, 5) ;
//			System.out.println(ans) ;
//			for (int i = 0; i < N; i++) {
//				for (int j = 0; j < M; j++) {
//					System.out.print(visitBFS[i][j] + " ");
//				}
//				System.out.println();
//			}
					
			checkClean = true;
			
			maTranKe = new int[demVetBan][demVetBan];//tao ma tran ke 		
			taoMaTranKe();
			
//			for (int i = 0; i < demVetBan ; i++) {
//				for (int j = 0; j < demVetBan ; j++) {
//					System.out.print(maTranKe[i][j] + " ");
//				}
//				System.out.println();
//			}
//			System.out.println();
			
			visitBackTrack = new int[demVetBan];
			minCanTim = Integer.MAX_VALUE;
//			for (int i = 0; i < demVetBan; i++) {
//				backtrack(1, 0, 0) ; 
//			}
			backtrack(1, 0, 0);
			System.out.println("Case #" + tc);
			if(checkClean == true){
				System.out.println(minCanTim);
			} else {
				System.out.println(-1);
			}
		}
		sc.close();
		//endFunc = System.currentTimeMillis();
		//System.out.println(endFunc - startFunc + " ms");
	}
	
	private static void taoMaTranKe() {
		for (int i = 0; i < demVetBan - 1; i++) {
			for (int j = i+1; j < demVetBan; j++) {
				maTranKe[i][j] = BFS(pos[i][0], pos[i][1], pos[j][0], pos[j][1]) ;
				maTranKe[j][i] = maTranKe[i][j] ;
				if(maTranKe[i][j] == -1){
					checkClean = false ;
				}
			}
		}
	}
	
	private static void visitBFS(){
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				visitBFS[i][j] = 0; 
			}
		}
	}
	

	private static void backtrack(int k, int cnt, int curNode){
		if( cnt >= minCanTim){
			return ;
		}
		
		if( k == demVetBan){
			minCanTim = Math.min( minCanTim, cnt ) ;
			return ;
		}
		visitBackTrack[0] = 1;
		for (int i = 1; i < demVetBan ; i++) { // vi tri robot la sach
			if( visitBackTrack[i] == 0 && maTranKe[curNode][i] != 0){
				visitBackTrack[i] = 1 ;
				backtrack(k+1, cnt + maTranKe[curNode][i], i);
				visitBackTrack[i] = 0;
			}
		}
		
	}

	static int BFS(int startX, int startY, int endX, int endY){
		qx.reset() ; 
		qy.reset() ;
		visitBFS() ;
		visitBFS[startX][startY] = 1;
		qx.enQueue(startX);
		qy.enQueue(startY);
		
		while(!qx.isEmpty()){
			int r = qx.deQueue() ;
			int c = qy.deQueue() ;
			
			for (int k = 0; k < 4; k++) {
				int newr = r + dx[k] ; 
				int newc = c + dy[k] ;
				
				if(newr >= 0 && newr < N && newc >= 0 && newc < M){
					if( visitBFS[newr][newc] == 0 && map[newr][newc] != 2){
						visitBFS[newr][newc] = visitBFS[r][c] + 1;
						qx.enQueue(newr);
						qy.enQueue(newc);
					}
					if( newr == endX && newc == endY){
						return visitBFS[r][c] ;//tra ve BFS r, c ; 
					}
				}
			}
		}
		return -1 ;
	}
}

Leave a Comment