uva10360 (rats attack)
Why can’t we go backwards… for once — James Halliday, ‘Ready Player One’
จากโจทย์ดังรูป
เอาละ ถ้าเราลอง brute force วนลูปตรงๆไปเลย จะได้ code ตามนี้
ซึ่งใช้ operation ถึง 1024² * 20,000 = 20,971M ใน worst case ( n = 20,000 ) … แน่นอนว่าติด time limit exceeded
ซึ่ง code ที่เราเขียนไป จะเป็นการคิดไปหน้าตรงๆ นั่นคือ ในแต่ละ จุด x y มีรังหนูไหนบ้างที่จะถูกทำลาย ?
แต่ถ้าเราลองคิดกลับหลังดูบ้างละ?
ถ้าเราลองคิดกลับหลัง นั่นคือ ในการทำลายแต่ละรังหนู สามารถวางระเบิดที่จุด x y ไหนได้บ้าง ?
โดยเราจะสร้างตารางขนาด 1024 * 1024 ขึ้นมา เพื่อเก็บว่าการวางระเบิดในจุด x y ใดๆ จะจัดการหนูไปได้กี่ตัว โดยหากหนูอยู่ในจุด i j แสดงว่าเราสามารถวางระเบิดในช่วง |x-i| ≤ d และ |y-j| ≤ d เพื่อทำลายหนูรังนั้นได้ … โดยเราจะบวกค่าจำนวนหนูในรังไปที่ตารางช่อง x y นั่นเอง
โอเค อธิบายอาจจะงงๆหน่อย เราลองมาดูโค้ดกัน
โดย operation ที่ใช้ไป = 1024² + 20,000 * 50² + 1024² = 52M ซึ่งเร็วพอที่จะเป็น Accepted answer ได้แล้วแหละ
