বাইনারি ম্যাট্রিক্স কে শূন্য ম্যাট্রিক্সে রূপান্তরের অপারেশন গণনা (C++ প্রোগ্রাম)

এটি সমাধান করার জন্য আমরা নিচের ধাপগুলো অনুসরণ করব:

• 4x2 আকারের dir অ্যারে সংজ্ঞায়িত করুন := {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}
• const int inf = 10^6
• getPos() ফাংশন সংজ্ঞায়িত করুন, যা i, j নিবে এবং i * c + j ফেরত দিবে।
• getCoord() ফাংশন সংজ্ঞায়িত করুন, যা x নিবে:
  • ret নামক একটি pair সংজ্ঞায়িত করুন
  • ret[0] := x / c
  • ret[1] := x mod c
  • ret ফেরত দিন
• মূল মেথড থেকে নিচের কাজগুলো করুন:
  • mask := 0
  • r := ম্যাট্রিক্সের সারি সংখ্যা
  • c := ম্যাট্রিক্সের কলাম সংখ্যা
  • last := r * c
  • i := 0 থেকে i < r পর্যন্ত লুপ:
    • j := 0 থেকে j < c পর্যন্ত লুপ:
      • mask := mask XOR (matrix[i][j] * 2^getPos(i, j))
  • 512 আকারের dist অ্যারে সংজ্ঞায়িত করুন এবং -1 দিয়ে ফিল করুন।
  • q নামে একটি কিউ সংজ্ঞায়িত করুন।
  • mask কে q-তে ইনসার্ট করুন।
  • dist[mask] := 0
  • while (q খালি নয়):
    • mask := q-এর প্রথম উপাদান
    • q থেকে ডিলিট করুন
    • i := 0 থেকে i < last পর্যন্ত লুপ:
      • coord := getCoord(i)
      • x := coord[0], y := coord[1]
      • nmask := mask
      • nmask := nmask XOR 2^i
      • k := 0 থেকে k < 4 পর্যন্ত লুপ:
        • nx := x + dir[k][0], ny := y + dir[k][1]
        • যদি nx এবং ny ম্যাট্রিক্সের রেঞ্জে না থাকে, তবে pokrač করুন।
        • pos := getPos(nx, ny)
        • nmask := nmask XOR (2^pos)
      • যদি dist[nmask] == -1 বা dist[nmask] > dist[mask] + 1:
        • dist[nmask] := dist[mask] + 1
        • nmask কে q-তে ইনসার্ট করুন
  • dist[0] ফেরত দিন।

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

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

3