Computer >> Máy Tính >  >> Lập trình >> C ++

Chương trình đếm số hoạt động để chuyển đổi ma trận nhị phân thành ma trận 0 trong C ++

Giả sử chúng ta có một ma trận nhị phân. Bây giờ hãy xem xét một phép toán trong đó chúng ta lấy một ô và lật nó và tất cả các ô lân cận của nó (lên, xuống, trái, phải). Chúng ta phải tìm số lượng phép toán tối thiểu cần thiết để ma trận chỉ chứa các số 0. Nếu không có giải pháp nào, hãy trả về -1.

Vì vậy, nếu đầu vào giống như

0
0
1
0

thì đầu ra sẽ là 3.

Chương trình đếm số hoạt động để chuyển đổi ma trận nhị phân thành ma trận 0 trong C ++

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

  • Xác định một dir mảng có kích thước:4 x 2:={{1, 0}, {0, 1}, {- 1, 0}, {0, - 1}}
  • const int inf =10 ^ 6
  • Xác định một hàm getPos (), điều này sẽ lấy i, j,
  • trả lại i * c + j
  • Xác định một hàm getCoord (), hàm này sẽ lấy x
    • Xác định một cặp ret
    • ret [0]:=x / c
    • ret [1]:=x mod c
    • trả lời lại
  • Từ phương thức chính, hãy làm như sau:
  • mặt nạ:=0
  • r:=số hàng của ma trận
  • c:=số cột của ma trận
  • cuối cùng:=r * c
  • để khởi tạo i:=0, khi i
  • để khởi tạo j:=0, khi j
  • mask:=mask XOR (matrix [i, j] * 2 ^ getPos (i, j))
  • Xác định một phân vùng có kích thước 512 và điền bằng -1
  • Xác định một hàng đợi q
  • chèn mặt nạ vào q
  • dist [mặt nạ]:=0
  • while (q không trống), thực hiện:
    • mask:=phần tử đầu tiên của q
    • xóa phần tử khỏi q
    • để khởi tạo i:=0, khi i
    • Xác định một cặp phối hợp
    • x:=coord [0]
    • y:=coord [1]
    • nmask:=mask
    • nmask:=nmask XOR 2 ^ i
    • để khởi tạo k:=0, khi k <4, cập nhật (tăng k lên 1), thực hiện:
      • nx:=x + dir [k, 0]
      • ny:=y + dir [k, 1]
      • nếu nx và ny không thuộc phạm vi ma trận, thì:
        • Bỏ qua phần sau, chuyển sang phần lặp tiếp theo
      • pos:=getPos (nx, ny)
      • nmask:=nmask XOR (2 ^ pos)
    • nếu dist [nmask] giống -1 hoặc dist [nmask]> dist [mask] + 1, thì:
      • dist [nmask]:=dist [mask] + 1
      • chèn nmask vào q
  • return dist [0]

    • Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

    Ví dụ 

    #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);
}

    Đầu vào 

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

    Đầu ra 

    3