โปรแกรมค้นหาจำนวนศัตรูสูงสุดจะถูกฆ่าเพื่อวางระเบิดใน C++?

สมมติว่าเรามีเมทริกซ์ 2D ที่มีค่าต่างกันสามค่า 2s, 1s และ 0s โดยที่ 2 หมายถึงศัตรู 1 หมายถึงกำแพงและ 0 หมายถึงเซลล์ว่าง เราต้องหาศัตรูให้ได้มากที่สุดโดยใช้ระเบิดลูกเดียว ระเบิดฆ่าศัตรูทั้งหมดในแถวและคอลัมน์เดียวกันจากจุดที่ปลูกจนกระทบผนัง และเราสามารถวางระเบิดได้เฉพาะในช่องว่างเท่านั้น

ดังนั้นหากอินพุตเป็นแบบ

จากนั้นผลลัพธ์จะเป็น 3 เนื่องจากเราสามารถวางระเบิดที่กล่องสีเขียวเพื่อฆ่าศัตรูได้สูงสุด 3 ตัว

• ยกเลิก :=0

• n :=จำนวนแถวของตาราง m :=จำนวนคอลัมน์ของกริด

• กำหนดอาร์เรย์ colCnt ขนาด m

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

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

    • ถ้า j เป็นศูนย์หรือ grid[i, j] เท่ากับ 1 แล้ว:

      • rowCnt :=0

      • ถ้า grid[i, j] เหมือนกับ 1 แล้ว:

        • k :=j + 1

      • มิฉะนั้น

        • k :=เจ

      • สำหรับ k

        • rowCnt :=rowCnt + 1 เมื่อ (grid[i, k] คือ 2) มิฉะนั้น 0

    • ถ้า i เป็นศูนย์ หรือ grid[i, j] เท่ากับ 1 แล้ว:

      • colCnt[j] :=0

      • ถ้า grid[i, j] เหมือนกับ 1 แล้ว:

        • k :=ผม + 1

      • มิฉะนั้น

        • k :=ผม

      • สำหรับ k

        • colCnt[j] :=colCnt[j] + 1 เมื่อ (grid[k, j] คือ 2) มิฉะนั้น 0

    • ถ้า grid[i, j] เหมือนกับ 0 แล้ว:

      • ret :=สูงสุดของ ret และ rowCnt + colCnt[j]

• รีเทิร์น

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

ตัวอย่าง

#include ใช้เนมสเปซ std;คลาสโซลูชัน {สาธารณะ:int แก้ปัญหา (เวกเตอร์<เวกเตอร์>&ตาราง) { int ret =0; int n =grid.size(); int m =n ? กริด[0].size() :0; int rowCnt =0; เวกเตอร์ colCnt(m); for (int i =0; i > v ={ {0,2,0,0}, {2,0,1,2}, {0,2,0,0}}; cout <<(ob.solve(v));}

อินพุต

ผลลัพธ์

3