# 2016多校第三場 HDU 5755 -开发者知识库

#### 有的讀者可能覺得程序寫的有點問題，建邊應該是別的點對當前點的貢獻，但是因為這個題的性質，這個問題可以不考慮

//// Created by Running Photon// Copyright (c) 2015 Running Photon. All rights reserved.//#include <algorithm>#include <cctype>#include <cmath>#include <cstdio>#include <cstdlib>#include <cstring>#include <iomanip>#include <iostream>#include <map>#include <queue>#include <string>#include <sstream>#include <set>#include <vector>#include <stack>#define ALL(x) x.begin(), x.end()#define INS(x) inserter(x, x,begin())#define ll long long#define CLR(x) memset(x, 0, sizeof x)using namespace std;const int inf = 0x3f3f3f3f;const int MOD = 3;const int maxn = 1e6   10;const int maxv = 1e3   10;const double eps = 1e-9;int a[maxv][maxv];int x[maxv];int mp[905];int all;void print() {    for(int i = 0; i < all; i  ) {        for(int j = 0; j <= all; j  ) {            printf("%d ", a[i][j]);        }        puts("");    }    puts("");}int Gauss(int equ, int var) {    int row, max_r, col;    // print();    for(row = 0, col = 0; col < var && row < equ; col  , row  ) {        max_r = row;        for(int i = row   1; i < equ; i  ) {            if(abs(a[i][col]) > abs(a[max_r][col])) {                max_r = i;            }        }        if(!a[max_r][col]) {            row--;            continue;        }        if(row != max_r) {            for(int j = 0; j <= var; j  ) {                swap(a[row][j], a[max_r][j]);            }        }        for(int i = row   1; i < equ; i  ) {            if(a[i][col]) {                int lcm = a[i][col] / __gcd(a[i][col], a[row][col]) * a[row][col];                int t1 = lcm / a[i][col];                int t2 = lcm / a[row][col];                for(int j = col; j <= var; j  ) {                    a[i][j] = ((a[i][j] * t1 - a[row][j] * t2) % MOD   MOD) % MOD;                }            }        }    }    // print();    // for(int i = row; i < equ; i  )    // if(a[i][var]) continue;    for(int i = var - 1; i >= 0; i--) {        x[i] = a[i][var];        for(int j = i   1; j < var; j  ) {            //            x[i] = ((x[i] - a[i][j] * x[j]) % MOD   MOD) % MOD;        }        //mod 3下的逆元就是其本身        x[i] = a[i][i] * x[i] % MOD;        // printf("x[%d] = %d\n", i, x[i]);    }}bool check(int u) {    return u >= 0 && u < all;}int main() {#ifdef LOCAL    freopen("C:\Users\Administrator\Desktop\in.txt", "r", stdin);    freopen("C:\Users\Administrator\Desktop\out.txt","w",stdout);#endif// ios_base::sync_with_stdio(0);    int T;    scanf("%d", &T);    while(T--) {        int n, m;        scanf("%d%d", &n, &m);        for(int i = 0; i < n; i  ) {            for(int j = 0; j < m; j  ) {                scanf("%d", &mp[i*m j]);            }        }        all = n * m;        CLR(a);        for(int i = 0; i < all; i  ) {            int u = i - m;            int d = i   m;            int l = i - 1;            int r = i   1;            a[i][i] = 2;            a[i][all] = (3 - mp[i]) % MOD;            if(check(u)) a[i][u] = 1;            if(check(d)) a[i][d] = 1;            if(check(l) && i % m != 0) a[i][l] = 1;            if(check(r) && i % m != m - 1) a[i][r] = 1;        }        Gauss(all, all);        std::vector<int> ans;        for(int i = 0; i < all; i  ) {            while(x[i]) {                x[i]--;                ans.push_back(i);            }        }        cout << ans.size() << endl;        for(int i = 0; i < ans.size(); i  ) {            int r = ans[i] / m;            int c = ans[i] % m;            printf("%d %d\n", r 1, c 1);        }    }    return 0;}

0条回复