test/aoj1308.test.cpp

Back to top page

• category: test
• View this file on GitHub
  • Last commit date: 2020-03-01 12:39:31+09:00
• see: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1308

Depends on

• math/binary_matrix.cpp
• memo/macro.hpp

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1308"
#include "../memo/macro.hpp"
#include "../math/binary_matrix.cpp"

signed main(void) {
   while(true) { 
        ll h, w, d;
        cin >> w >> h >> d;
        if(!w) break;
        vector<vector<ll>> s(h, vector<ll>(w));
        REP(i, h) REP(j, w) cin >> s[i][j];

        matrix<630> mat(h*w);
        REP(y, h) REP(x, w) {
            mat.dat[y*w+x][y*w+x] = 1;
            REP(i, h) REP(j, w) {
                if(abs(y-i)+abs(x-j) != d) continue;
                mat.dat[y*w+x][i*w+j] = 1;
            }
            mat.dat[y*w+x][h*w] = 1 - s[y][x];
        }

        bool ans = true;
        gauss_jordan(mat);
        REP(i, h*w) {
            bool flag = true;
            REP(j, h*w) if(mat.dat[i][j]) { flag = false; break; } 
            if(flag && mat.dat[i][h*w] == 1) ans = false; 
        }

        if(ans) cout << 1 << endl;
        else cout << 0 << endl;
    }

    return 0;
}

#line 1 "test/aoj1308.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1308"
#line 1 "memo/macro.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using PII = pair<ll, ll>;
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;
const ll INF = 1LL<<60;
#line 1 "math/binary_matrix.cpp"
// BEGIN CUT
// GF(2)の行列
template<int width=64>
struct matrix {
    int h, w;
    vector<bitset<width>> dat;
    matrix() {}
    matrix(int h) : h(h), w(width), dat(h) {}

    matrix& operator+=(const matrix& r) {
        assert(h==r.h && w==r.w);
        REP(i, h) dat[i] ^= r.dat[i];
        return *this;
    }
    matrix& operator-=(const matrix& r) {
        assert(h==r.h && w==r.w);
        REP(i, h) dat[i] ^= r.dat[i];
        return *this;
    }
    matrix& operator*=(const matrix& r) {
        assert(w==r.h);
        matrix ret(h, w);
        REP(i, h) REP(j, r.w) REP(k, w) {
            ret.dat[i][j] ^= dat[i][k] & r.dat[k][j];
        }
        return (*this) = ret;
    }
    matrix operator+(const matrix& r) { return matrix(*this) += r; }
    matrix operator-(const matrix& r) { return matrix(*this) -= r; }
    matrix operator*(const matrix& r) { return matrix(*this) *= r; }
    bool operator==(const matrix& a) { return dat==a.dat; }
    bool operator!=(const matrix& a) { return dat!=a.dat; }

    friend matrix pow(matrix p, ll n) {
        matrix ret(p.h, p.w);
        REP(i, p.h) ret.dat[i][i] = 1;
        while(n > 0) {
            if(n&1) {ret *= p; n--;}
            else {p *= p; n >>= 1;}
        }
        return ret;
    }
    // 階段行列を求める O(HW^2)
    friend int gauss_jordan(matrix &a) {
        int rank = 0;
        REP(i, a.w) {
            int pivot = -1;
            FOR(j, rank, a.h) if(a.dat[j][i] != 0) { pivot = j; break; }
            if(pivot == -1) continue;
            swap(a.dat[rank], a.dat[pivot]);
            REP(j, a.h) if(j != rank && a.dat[j][i] != 0) {
                a.dat[j] ^= a.dat[rank];
            }
            rank++;
        }
        return rank;
    }

    friend ostream &operator<<(ostream& os, matrix a) {
        REP(i, a.h) {
            REP(j, a.w) os << a.dat[i][j] << " ";
            os << endl;
        }
        return os;
    }
};
// END CUT
#line 4 "test/aoj1308.test.cpp"

signed main(void) {
   while(true) { 
        ll h, w, d;
        cin >> w >> h >> d;
        if(!w) break;
        vector<vector<ll>> s(h, vector<ll>(w));
        REP(i, h) REP(j, w) cin >> s[i][j];

        matrix<630> mat(h*w);
        REP(y, h) REP(x, w) {
            mat.dat[y*w+x][y*w+x] = 1;
            REP(i, h) REP(j, w) {
                if(abs(y-i)+abs(x-j) != d) continue;
                mat.dat[y*w+x][i*w+j] = 1;
            }
            mat.dat[y*w+x][h*w] = 1 - s[y][x];
        }

        bool ans = true;
        gauss_jordan(mat);
        REP(i, h*w) {
            bool flag = true;
            REP(j, h*w) if(mat.dat[i][j]) { flag = false; break; } 
            if(flag && mat.dat[i][h*w] == 1) ans = false; 
        }

        if(ans) cout << 1 << endl;
        else cout << 0 << endl;
    }

    return 0;
}

Back to top page