136 lines
3.1 KiB
C++
136 lines
3.1 KiB
C++
#include <bits/stdc++.h>
|
|
|
|
#define FOR(i, n) for(lli i = 0; i < (lli)(n); ++i)
|
|
#define FORU(i, a, b) for(lli i = (lli)(a); i < (lli)(b); ++i)
|
|
#define FORD(i, a, b) for(lli i = (lli)(b)-1; i >= (lli)(a); --i)
|
|
#define ALL(x) (x).begin(), (x).end()
|
|
|
|
#define X(A) get<0>(A)
|
|
#define Y(A) get<1>(A)
|
|
#define Z(A) get<2>(A)
|
|
#define W(A) get<3>(A)
|
|
|
|
#define mt make_tuple
|
|
#define pb push_back
|
|
|
|
|
|
|
|
using namespace std;
|
|
using lli = long long int;
|
|
|
|
using pii = tuple<lli, lli>;
|
|
using piii = tuple<lli, lli, lli>;
|
|
using vi = vector<lli>;
|
|
using vii = vector<pii>;
|
|
using viii = vector<piii>;
|
|
using vvi = vector<vi>;
|
|
using vvii = vector<vii>;
|
|
using vviii = vector<viii>;
|
|
using vb = vector<bool>;
|
|
using vvb = vector<vb>;
|
|
// =====
|
|
|
|
const int DIM = 50 * 50 + 1;
|
|
int nbRows, nbCols, nbDim;
|
|
|
|
typedef bitset<DIM> Matr;
|
|
|
|
struct PermVect {
|
|
vector<Matr> v;
|
|
vector<int> lineId;
|
|
|
|
PermVect(){}
|
|
PermVect(size_t n) {
|
|
v.resize(n);
|
|
lineId.resize(n);
|
|
FOR(i, lineId.size()) lineId[i] = i;
|
|
}
|
|
|
|
Matr& operator[](size_t pos) { return v[lineId[pos]]; }
|
|
const Matr& operator[](size_t pos) const { return v[lineId[pos]]; }
|
|
void swapRow(size_t i, size_t j) {
|
|
swap(lineId[i], lineId[j]);
|
|
}
|
|
};
|
|
|
|
PermVect crosses;
|
|
|
|
inline size_t at(int row, int col) {
|
|
return row * nbCols + col;
|
|
}
|
|
|
|
void dump() {
|
|
FOR(rowId, nbDim) {
|
|
const Matr& row = crosses[rowId];
|
|
FOR(pos, nbDim)
|
|
printf("%c", row[pos]?'1':'0');
|
|
printf(" %c\n", row[nbDim]?'1':'0');
|
|
}
|
|
puts("===");
|
|
}
|
|
|
|
bool solve() {
|
|
for(int trigAt=0; trigAt < nbDim; ++trigAt) {
|
|
bool found = false;
|
|
for(int dim=trigAt; dim < nbDim; ++dim) {
|
|
if(!crosses[dim][trigAt])
|
|
continue;
|
|
found = true;
|
|
crosses.swapRow(trigAt, dim);
|
|
for(int nDim=trigAt+1; nDim < nbDim; ++nDim) {
|
|
if(crosses[nDim][trigAt])
|
|
crosses[nDim] ^= crosses[trigAt];
|
|
}
|
|
break;
|
|
}
|
|
if(!found)
|
|
return false;
|
|
}
|
|
for(int dim=nbDim-1; dim >= 0; --dim) {
|
|
for(int nDim=dim-1; nDim >= 0; --nDim) {
|
|
if(crosses[nDim][dim])
|
|
crosses[nDim] ^= crosses[dim];
|
|
}
|
|
}
|
|
return true;
|
|
}
|
|
|
|
int main(void) {
|
|
scanf("%d%d", &nbRows, &nbCols);
|
|
nbDim = nbRows * nbCols - 1;
|
|
crosses = PermVect(nbDim);
|
|
FOR(row, nbRows) {
|
|
FOR(col, nbCols) {
|
|
FOR(i, nbCols)
|
|
crosses[at(row, col)].set(at(row, i));
|
|
FOR(i, nbRows)
|
|
crosses[at(row, col)].set(at(i, col));
|
|
}
|
|
}
|
|
|
|
FOR(row, nbRows) {
|
|
getchar();
|
|
FOR(col, nbCols)
|
|
crosses[at(row, col)][nbDim] = getchar() == 'B';
|
|
}
|
|
|
|
|
|
if(!solve()) {
|
|
dump();
|
|
puts("No");
|
|
}
|
|
else {
|
|
puts("Yes");
|
|
set<int> ids;
|
|
FOR(row, nbDim)
|
|
if(crosses[row][nbDim])
|
|
ids.insert(row);
|
|
printf("%lu\n", ids.size());
|
|
FOR(i, nbDim) {
|
|
if(ids.find(crosses.lineId[i]) != ids.end())
|
|
printf("%lld %lld\n", (i/nbCols) + 1, (i%nbCols) + 1);
|
|
}
|
|
}
|
|
return 0;
|
|
}
|