คะแนนสูงสุดหลังจากพลิก Binary Matrix สูงสุด K ครั้งใน C++

ในปัญหานี้ เราได้รับอาร์เรย์ 2 มิติ arr[] ซึ่งประกอบด้วยค่าบูลีน (เช่น 0 และ 1) และจำนวนเต็ม K งานของเราคือสร้างโปรแกรมเพื่อค้นหาคะแนนสูงสุดหลังจากพลิกเมทริกซ์ไบนารีที่ K ครั้งใน C++.

คำอธิบายปัญหา − ในที่นี้ สำหรับอาร์เรย์ 2 มิติและการเคลื่อนที่ k เราจำเป็นต้องค้นหาตัวเลขที่สร้างโดยองค์ประกอบของอาร์เรย์ ในแต่ละการเคลื่อนไหว เราจะนำแถวหรือคอลัมน์และพลิกองค์ประกอบทั้งหมดของแถวหรือคอลัมน์ ตัวเลือกจะทำขึ้นเพื่อจำไว้ว่าเราจำเป็นต้องเพิ่มจำนวนสูงสุดที่สร้างขึ้นหลังจาก K พลิกในแถวของเมทริกซ์ และเราต้องคืนค่าผลรวมของตัวเลขทั้งหมดที่สร้างในแถว

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

อินพุต

arr[][] ={ {1, 0, 0}, {0, 1, 1}, {1, 0, 1}}K =2

ผลลัพธ์

19

คำอธิบาย

เรามีสองพลิก

พลิกครั้งแรก – เราจะพลิกองค์ประกอบแถวที่ 2 สิ่งนี้จะทำให้อาร์เรย์

พลิกครั้งที่สอง - เราจะพลิกองค์ประกอบคอลัมน์ที่ 2 สิ่งนี้จะทำให้อาร์เรย์

{{1, 1, 0},{1, 1, 0},{1, 1, 1}}

หมายเลขสุดท้ายที่สร้างในแต่ละแถวคือ 6, 6, 7

ผลรวมสูงสุด =19

แนวทางการแก้ปัญหา

ในการแก้ปัญหา เราต้องสร้างองค์ประกอบของคอลัมน์แรกเป็น 1 ก่อน เนื่องจาก 1 ที่คอลัมน์ ith จะส่งผลให้ 2i ซึ่งจะเป็นจำนวนที่เป็นไปได้มากที่สุด (หากพิจารณาหนึ่งชุดบิต) ดังนั้น คอลัมน์ซ้ายสุดจะต้องมีจำนวนสูงสุด 1 (set bits ) เพื่อให้ผลรวมสูงสุด จากนั้นเราจะไปหาองค์ประกอบอื่นของแต่ละแถว

เพื่อตรวจสอบว่าต้องพลิกแถวหรือคอลัมน์ เราต้องตรวจสอบค่าอื่นๆ ในคอลัมน์ นั่นคือองค์ประกอบแรกทั้งหมดของแถว ถ้าจำนวน 0 มากกว่า 1 เราจะพลิกคอลัมน์ไม่เช่นนั้นจะพลิกแถว

ในการแก้ปัญหา เราจะใช้โครงสร้างข้อมูลแผนที่

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

ตัวอย่าง

#include ใช้เนมสเปซ std;const int row =3;const int col =3;int MaxSumAfterFlip(int mat[row][col], int K) { map พลิกค่า; int updateVal, MaxSum =0; สำหรับ (int i =0; i ::iterator it =flipValues.begin(); ในขณะที่ (K> 0 &&it !=flipValues.end()) { int updateIndex =it->second; สำหรับ (int j =0; j  0 &&ศูนย์> คน) { MaxSum +=ศูนย์ * pow (2, (col - j - 1)); เค--; } อื่น MaxSum +=คน * pow(2, (col - j - 1)); } return MaxSum;}int main() { int mat[row][col] ={{1, 0, 0 },{0, 1, 1},{1, 0, 1}}; int K =2; cout<<"คะแนนสูงสุดหลังจากพลิกเมทริกซ์สูงสุด K ครั้งคือ "< 
ผลลัพธ์
 
คะแนนสูงสุดหลังจากพลิกเมทริกซ์สูงสุด K ครั้งคือ 19