โปรแกรมนับจำนวนการดำเนินการเพื่อแปลงเมทริกซ์ไบนารีเป็นเมทริกซ์ศูนย์ใน C++

สมมติว่าเรามีเมทริกซ์ไบนารี ตอนนี้ให้พิจารณาการดำเนินการที่เรานำเซลล์หนึ่งเซลล์แล้วพลิกเซลล์และเซลล์ที่อยู่ใกล้เคียงทั้งหมด (ขึ้น ลง ซ้าย ขวา) เราต้องหาจำนวนการดำเนินการขั้นต่ำที่จำเป็นเพื่อให้เมทริกซ์มี 0s เท่านั้น หากไม่มีวิธีแก้ปัญหา ให้คืนค่า -1

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

แล้วผลลัพธ์จะเป็น 3

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

• กำหนดขนาดอาร์เรย์ของอาร์เรย์:4 x 2 :={{1, 0}, {0, 1}, { - 1, 0}, {0, - 1}}
• const int inf =10^6
• กำหนดฟังก์ชัน getPos() ซึ่งต้องใช้ i, j,
• คืนค่า i * c + j
• กำหนดหนึ่งฟังก์ชัน getCoord() ซึ่งจะใช้เวลา x
  • กำหนดหนึ่งคู่ ret
  • ret[0] :=x / c
  • ret[1] :=x mod c
  • คืนสินค้า
• จากวิธีหลัก ให้ทำดังนี้:
• หน้ากาก :=0
• r :=จำนวนแถวของเมทริกซ์
• c :=จำนวนคอลัมน์ของเมทริกซ์
• สุดท้าย :=r * c
• สำหรับการเริ่มต้น i :=0 เมื่อฉัน
• สำหรับการเริ่มต้น j :=0 เมื่อ j
• มาสก์ :=มาสก์ XOR (เมทริกซ์[i, j] * 2^getPos(i, j))

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

ตัวอย่าง

#include
using namespace std;
int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int c;
int r;
int last;
const int inf = 1e6;

int getPos(int i, int j){
   return i * c + j;
}
pair getCoord(int x){
   pair ret;
   ret.first = x / c;
   ret.second = x % c;
   return ret;
}

int solve(vector>& matrix) {
   int mask = 0;
   r = matrix.size();
   c = r ? matrix[0].size() : 0;
   last = r * c;
   for(int i = 0; i < r; i++){
      for(int j = 0; j < c; j++){
         mask ^= (matrix[i][j] << getPos(i, j));
      }
   }
   vector dist(1 << 9, -1);
   queue q;
   q.push(mask);
   dist[mask] = 0;
   while(!q.empty()){
      mask = q.front();
      q.pop();
     
      for(int i = 0; i < last; i++){
         pair coord = getCoord(i);      
         int x = coord.first;
         int y = coord.second;
         
         int nmask = mask ;
         nmask ^= (1 << i);
         for(int k = 0; k < 4; k++){
            int nx = x + dir[k][0];
            int ny = y + dir[k][1];
            if(nx < 0 || nx >= r || ny < 0 || ny >= c)
               continue;
            int pos = getPos(nx, ny);
            nmask ^= (1 << pos);
         }
         
         if(dist[nmask] == -1 || dist[nmask] > dist[mask] + 1){
            dist[nmask] = dist[mask] + 1;
            q.push(nmask);
         }
      }
   }
   return dist[0];
}
int main(){
   vector> v = {{0, 0},{1, 0}};
   cout << solve(v);
}

อินพุต

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

ผลลัพธ์

3