Module: Tìm kiếm theo chiều sâu. DFS


Problem

8 /12


DFS đệ quy

Problem

Cho ma trận N (1 <= N <= 100) nhân với M (1 <= M <= 100). Ma trận chứa ‘.’ – ô trống và ‘#’ – các ô không thể truy cập được. Bạn chỉ có thể di chuyển lên, xuống, trái và phải. Đưa ra q truy vấn: số hàng và số cột, nếu ô này – ‘#’, thì nó trở thành ‘.’, nếu không thì – ‘#’. Đối với mỗi truy vấn trong số q truy vấn, hãy xác định xem có thể truy cập ô tx;ty từ ô Sx;Sy . Xuất trên mỗi dòng “Có”, nếu có thể truy cập được và “Không” - nếu không thì. Đảm bảo rằng ô Sx; Sy và ô tx; ty không ‘#’ ô trong mỗi yêu cầu.
Nhập dữ liệu.
Trên dòng đầu tiên, nhập các số Sx (1 <= Sx <= 100), Sy (1 <= Sy <= 100), tx (1 <= tx <= 100), ty (1 <= ty <= 100), N (1 <= N <= 100), M(1 <= M <= 100 ) và q (1 <= q <= 100). N dòng tiếp theo đưa ra một ma trận trong đó ‘.’ – ô trống và ‘#’ – một ô không thể được truy cập. Q dòng tiếp theo ghi số hàng và số cột cần thay đổi.
 
Đầu ra.
In cho từng q truy vấn “Có”, nếu từ ô Sx; Sy vào ô tx; ty có thể bị đánh, “Không” – mặt khác.
 
 
Giải thích:
Sau yêu cầu đầu tiên, ma trận sẽ như thế này:
.  .  #
# # .
###
Không có đoạn nào từ điểm 1;1 đến 2;3, do đó, chúng tôi in “No”.

Sau yêu cầu thứ hai, ma trận sẽ như sau:
.  .  #
# .  .
###
Có một đoạn từ điểm 1;1 đến 2;3, vì vậy chúng tôi xuất ra “Yes”. Con đường chúng ta có thể đi theo được đánh dấu.

(с) Vsevolod Shaldin
 
Đầu vào Đầu ra
1 1 2 3 3 3 2
.##
##.
###
1 2
2 2
Không