BFS / BSearch

[vzsky]

statement

ให้ grid n*m แต่ละช่องเป็น wall, empty, goal ขอบ grid ทุกขอบถือเป็น wall ถือว่ามี wall จำนวน w ที่
ถ้าด้านหลังเป็น wall, สามารถถีบตัวเองเพื่อเคลื่อนไปไหนก็ได้ใน row / column นั้น
มี goal แค่ g ที่
given (x, y) หาว่าจาก goal g ที่ ไปได้กี่ที่ + จากทุก goal ที่ไปได้ต้องกระโดดเฉลี่ยกี่ครั้ง

concept

bfs, binary search -> O((w+n+m)log(nm)) (มั้ง)

[vzsky]

solutions

• bfs จาก goal ทุกอันไปจนเจอ initial position (จะใช้ reverse edge ของที่โจทย์บอก) ซึ่งหา edge ทั้งหมด (ไม่เกิน 4 edge) จากจุดใดๆได้ด้วย bsearch

subtasks

• no wall
• O(NMG) bfs ทางปกติ
• O(NM) bfs ไม่ต้อง bsearch ได้ space พอเก็บ edge

[vzsky]

แก้ subtask หน่อยครับ อันเก่าผิด แก้เป็น

• no wall -> O(1)
• O(NM) bfs ทางปกติ หรือ reverse edge ก้ได้
• O(v log(w)log(nm))
• solution เต็ม -> O(vlog(w))

โดยที่ v = n+m+w
อาจจะให้ g = 1 ไปเลยเพื่อลด implementation work เพราะไม่ได้เกี่ยวอะไรกับ task เท่าไหร่ เดะดูอีกที