Nâng cao bài toán BUS2 NTUCoders

[Hien_Nguyen (Hiển Nguyễn)]

Link bài BUS2: http://ntucoder.net/Problem/Details/4486

Đề gốc

Thành phố Y có hệ thống giao thông gồm n đường ngang và m đường dọc chạy 2 chiều. Các đường ngang được đánh số từ 1 đến n từ trên xuống dưới và đường dọc được đánh số từ 1 đến m từ trái sang phải. Các đường ngang và đường dọc cắt nhau tạo thành n x m giao lộ (ngã hai, ngã ba, ngã tư) như hình bên dưới. Tại các giao lộ (kể cả ngã hai) đều có bố trí đèn giao thông gồm hai màu xanh đỏ. Đèn xanh là được đi và đèn đỏ là đứng lại. Điểm đặc biệt của đèn ở đây là khi đèn đỏ thì xe ở cả bốn hướng đều phải dừng lại chờ, khi đèn xanh thì xe ở bốn hướng đều được đi (thẳng, rẽ trái, rẽ phải đều được). Cứ sau mỗi 1 phút thì đèn sẽ chuyển từ xanh sang đỏ và ngược lại.

Một chiếc xe khách muốn vào thành phố ở giao lộ (1,1) và ra khỏi thành phố ở giao lộ (n, m). Thời gian để xe khách di chuyển từ một giao lộ đến giao lộ kế cận là 1 phút. Khi xe vừa trờ tới một giao lộ thì lúc đó đèn cũng chuyển màu, nếu là màu xanh thì xe tiếp tục đi, nếu là màu đỏ thì xe phải dừng lại chờ 1 phút để chuyển xanh thì mới được đi tiếp. Bạn hãy tính xem thời gian nhanh nhất để xe đi ra khỏi thành phố là bao nhiêu nhé.

Dữ liệu nhập:

• Dòng đầu tiên là hai số nguyên n và m (2 ≤ n, m ≤ 1000)

• Trong n dòng tiếp theo, tại dòng thứ i gồm m số nguyên aij là tình trạng đèn tại thời điểm xe bắt đầu vào thành phố: aij = 1 nghĩa là tại giao lộ (i, j) có đèn màu xanh, aij = 0 là có đèn màu đỏ.

Dữ liệu xuất:

• Là một số nguyên xác định số phút sớm nhất mà xe ra khỏi thành phố.

Ví dụ

• input

3 5
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

output

13

• input

3 5
1 0 0 0 0
0 0 0 0 0
1 0 1 0 1

output

6

Test 1: Đi theo hướng (1, 1) -> (1, 5) -> (3, 5)

Khi xe đến mỗi giao lộ thì đèn đều màu đỏ nên phải chờ ở tất cả 7 đèn tốn 7 phút. Cộng thêm thời gian di chuyển là 6 phút. Tổng cộng 13 phút.

Test 2: Đi theo hướng (1, 1) -> (3, 1) -> (3, 5)

Khi xe đến mỗi giao lộ thì đèn đều màu xanh nên không phải chờ đèn nào. Chỉ tính thời gian di chuyển là 6 phút.

Đề gốc là “Điểm đặc biệt của đèn ở đây là khi đèn đỏ thì xe ở cả bốn hướng đều phải dừng lại chờ, khi đèn xanh thì xe ở bốn hướng đều được đi (thẳng, rẽ trái, rẽ phải đều được). Cứ sau mỗi 1 phút thì đèn sẽ chuyển từ xanh sang đỏ và ngược lại.”

Nhưng nếu thay đổi thời gian chờ đèn đỏ là 1p, chờ đèn xanh có thể lên 2-3p và khi có đèn xanh, xe chưa chắc đã đi, thì làm thế nào để tìm được đường ra khỏi tp nhanh nhất ạ?
Và giảm m, n: 2 <= m, n <= 50

Em đã thử quy hoạch động cho từng hàng, từng cột (Và chắc chắn là sai rồi vì thay vì chờ rồi gặp đèn đỏ liên tục, có khi đi vòng nhanh hơn mà)

Sau đó, em xét cái hàng đợi queue, ban đầu cho {1, 1, 0} (lần lượt là i, j, time), sau đó xét 5 cạnh kề (vị trí đó và 4 điểm chung cạnh) rồi cứ BFS loang đi hết, và chạy quá thời gian trong khi 2 <= m, n <= 50 thôi.

[kisuluoibieng (Tên Gì Cũng Được)]

bài này theo mình nghĩ là vẫn dùng quy hoạch động, tuy nhiên với công thức truy hồi có chút biến tấu

1. để ý kĩ thì chi phí để đi từ ngã tư này đến ngã tư kế bên luôn luôn là nhỏ nhất, không thể nào có đường vòng mà ngắn hơn
2. như vậy thì đường đi tối ưu vẫn sẽ là đi sang phải hoặc đi xuống (theo như hình cho dễ tưởng tượng)

từ đó, ra có chi phí đi tới ngã tư
cost[x,y] = min(goDown, goRight)
với
goDown = cost[x-1, y] + thời gian chờ đèn + 1p
goRight = cost[x, y-1] + thời gian chờ đèn + 1p

à, tới đây mới có vấn đề để bàn
thời gian chờ đèn là hên xui, ví dụ đèn switch mỗi 5p, thì có thể tới đó chờ 0, 1, 2, 3, 4, 5
vậy làm sao biết?
tất nhiên là tính toán, việc tính toán khá đơn giản, bạn đã biết thời gian để bạn đến được ngã tư A, bạn biết thời gian swtich của ngã tư A, vậy là tính được rồi

ví dụ đèn swtch 5p, bạn đến được ngã tư A đó sau 28p, như vậy 5(x) + 5(đ) + 5(x) + 5(đ) + 5(x) + 5(đ)
bạn bị lọt vào 5p đèn đỏ, như vây phải chờ đủ 30p => thời gian chờ để được đi là 2p

[ggwp (Quang Phú Nguyễn)]

Bài này dùng Dijkstra cũng được, xử lý thêm một chút chỗ đèn giữ nguyên hay đổi màu là AC.