ตำแหน่งกบหลังจาก T วินาทีใน C++

สมมติว่าเรามีต้นไม้ที่ไม่มีทิศทางหนึ่งต้นที่ประกอบด้วยจุดยอด n จุด จุดยอดมีตัวเลขตั้งแต่ 1 ถึง n ตอนนี้กบเริ่มกระโดดจากจุดยอด 1 กบสามารถกระโดดจากจุดยอดปัจจุบันไปยังจุดยอดอื่นที่ไม่ได้เยี่ยมชมหากอยู่ติดกันในหนึ่งวินาที กบไม่สามารถกระโดดกลับไปที่จุดสุดยอดได้ ในกรณีที่กบสามารถกระโดดข้ามจุดยอดได้หลายจุด มันจะกระโดดข้ามไปยังจุดใดจุดหนึ่งแบบสุ่ม

โดยที่ความน่าจะเป็นเท่ากัน มิฉะนั้น เมื่อกบไม่สามารถข้ามไปยังจุดยอดใดๆ ที่ไม่ได้เยี่ยมชมได้ ก็จะกระโดดข้ามจุดยอดเดียวกันตลอดไป

ต้นไม้จะได้รับเป็นอาร์เรย์ของขอบ เราต้องหาความน่าจะเป็นที่หลังจากนั้น t วินาทีกบจะอยู่บนเป้าหมายจุดยอด

ดังนั้น ถ้าอินพุตเป็นเหมือน n คือ 7, t คือ 2, เป้าหมายคือ 4 และต้นไม้ก็เหมือนกับ −

จากนั้นผลลัพธ์จะเป็น 0.1666 จากกราฟ กบเริ่มต้นที่จุดยอด 1 โดยกระโดดด้วยความน่าจะเป็น 0.3333 ไปยังจุดยอด 2 หลังจาก 1 วินาที จากนั้นกระโดดด้วยความน่าจะเป็น 0.5 ที่จุดยอด 4 หลังจากวินาทีที่ 2 ดังนั้นความน่าจะเป็นของกบจะอยู่บนจุดยอด 4 หลังจาก 2 วินาทีคือ 0.3333 * 0.5 =1.6665.

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ยกเลิก :=1

• กำหนดการเยี่ยมชมหนึ่งชุด

• กำหนดฟังก์ชัน dfs() ซึ่งจะใช้โหนด เริ่มต้น รายการขอบ g เวลา t หนึ่งสแต็ก st

• ถ้าโหนดเป็นสมาชิกของการเยี่ยมชมแล้ว −

  • คืนค่าเท็จ

• แทรกโหนดเข้าเยี่ยมชม

• ถ้าโหนดเหมือนกับ 1 แล้ว −

  • tt :=เวลา โอเค :=จริง

  • คืนความจริง

• สำหรับการเริ่มต้น i :=0 เมื่อ i

  • แทรก g[node, i] ลงใน st

  • ถ้า dfs(g[node, i], start, g, time + 1, t, st) เป็นจริง −

    • คืนความจริง

  • ลบองค์ประกอบออกจาก st

• คืนค่าเท็จ

• จากวิธีหลัก ให้ทำดังต่อไปนี้ −

• ยกเลิก :=1

• โอเค :=เท็จ

• กำหนดอาร์เรย์ของกราฟรายการขนาด n + 1

• กำหนดอาร์เรย์ของรายการ graph2 ขนาด n + 1

• สำหรับการเริ่มต้น i :=0 เมื่อ i <ขนาดขอบ อัปเดต (เพิ่ม i ขึ้น 1) ทำ -

  • แทรก edge[i, 1] ที่ส่วนท้ายของกราฟ[edges[i, 0]]

  • แทรก edge[i, 0] ที่ส่วนท้ายของกราฟ[edges[i, 11]]

• กำหนดหนึ่งสแต็ก st

• dfs(เป้าหมาย เป้าหมาย กราฟ 0, t, st)

• ในขณะที่ (ไม่ใช่ st ว่างเปล่า) ทำ -

  • โหนด :=องค์ประกอบด้านบนของ st

  • sz :=ขนาดของกราฟ[โหนด]

  • ถ้าโหนดไม่เท่ากับ 1 แล้ว −

    • (ลด sz ลง 1)

  • ret :=ret * (1.0 / sz)

  • ลบองค์ประกอบออกจาก st

• ถ้า tt> t แล้ว −

  • คืนค่า 0

• ถ้า tt เหมือนกับ t แล้ว −

  • รีเทิร์น

• ถ้า tt =1 แล้ว −

  • คืนค่า 0

• return (ถ้า tt 1 แล้ว 0, มิฉะนั้น ret)

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#include ใช้เนมสเปซ std;class Solution { สาธารณะ:double ret =1; บูลโอเค; set เยี่ยมชม; int tt; bool dfs (โหนด int, int start, vector g[], int time, int t, stack&st){ if (visited.count (node)) คืนค่าเท็จ; visit.insert(โหนด); ถ้า (โหนด ==1) { tt =เวลา; ตกลง =จริง; คืนค่าจริง; } for (int i =0; i >&ขอบ, int t, เป้าหมาย int){ ret =1; ตกลง =เท็จ; เวกเตอร์ กราฟ[n + 1]; เวกเตอร์ graph2[n + 1]; สำหรับ (int i =0; i  st; dfs(เป้าหมาย, เป้าหมาย, กราฟ, 0, t, st); ในขณะที่ (!st.empty()) { โหนด int =st.top(); double sz =(double) กราฟ[node].size(); ถ้า (โหนด !=1) sz--; ยกเลิก *=(1.0 / sz); st.pop(); } ถ้า (tt> t) คืนค่า 0; ถ้า (tt ==t) กลับ ret; if (tt =1) คืนค่า 0; ส่งคืน tt  1 ? 0 :ยกเลิก; }};main(){ โซลูชัน ob; เวกเตอร์<เวกเตอร์> v ={{1,2},{1,3},{1,7},{2,4},{2,6},{3,5}}; cout <<(ob.frogPosition(7,v,2,4));}

อินพุต

ผลลัพธ์

0.166667