CSU 多校训练第二场 J Pinemi Puzzles

传送门：http://acm.csu.edu.cn:20080/csuoj/problemset/problem?pid=2279

题意：

代码：

#include <set>

#include <map>

#include <deque>

#include <queue>

#include <stack>

#include <cmath>

#include <ctime>

#include <bitset>

#include <cstdio>

#include <string>

#include <vector>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

/**

 *　　　　　　　　┏┓　　 　┏┓

 * 　　　　　　　┏┛┗━━━━━━━┛┗━━━┓

 * 　　　　　　　┃　　　　　　　┃ 　

 * 　　　　　　　┃　　　━　　 　┃

 * 　　　　　　　┃　＞　　　＜　┃

 * 　　　　　　　┃　　　　　　　┃

 * 　　　　　　　┃...　⌒　... 　┃

 * 　　　　　　　┃　　　　　　　┃

 * 　　　　　　　┗━┓　　　┏━┛

 * 　　　　　　　　　┃　　　┃　Code is far away from bug with the animal protecting　　　　　　　　　　

 * 　　　　　　　　　┃　　　┃   神兽保佑,代码无bug

 * 　　　　　　　　　┃　　　┃　　　　　　　　　　　

 * 　　　　　　　　　┃　　　┃  　　　　　　

 * 　　　　　　　　　┃　　　┃

 * 　　　　　　　　　┃　　　┃　　　　　　　　　　　

 * 　　　　　　　　　┃　　　┗━━━┓

 * 　　　　　　　　　┃　　　　　　　┣┓

 * 　　　　　　　　　┃　　　　　　　┏┛

 * 　　　　　　　　　┗┓┓┏━┳┓┏┛

 * 　　　　　　　　　　┃┫┫　┃┫┫

 * 　　　　　　　　　　┗┻┛　┗┻┛

 */

typedef long long LL;

typedef pair<LL, LL> pLL;

typedef pair<LL, int> pLi;

typedef pair<int, LL> pil;;

typedef pair<int, int> pii;

typedef unsigned long long uLL;

#define lson l,mid,rt<<1

#define rson mid+1,r,rt<<1|1

#define bug printf("*********\n")

#define FIN freopen("input.txt","r",stdin);

#define FON freopen("output.txt","w+",stdout);

#define IO ios::sync_with_stdio(false),cin.tie(0)

#define debug1(x) cout<<"["<<#x<<" "<<(x)<<"]\n"

#define debug2(x,y) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<"]\n"

#define debug3(x,y,z) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<" "<<#z<<" "<<z<<"]\n"

LL read() {

    int x = , f = ; char ch = getchar();

    while(ch < '' || ch > '') {

        if(ch == '-')f = -;

        ch = getchar();

    }

    while(ch >= '' && ch <= '') {

        x = x *  + ch - '';

        ch = getchar();

    }

    return x * f;

}

const double eps = 1e-;

const int mod = 1e9 + ;

const int maxn = 3e5 + ;

const int INF = 0x3f3f3f3f;

const LL INFLL = 0x3f3f3f3f3f3f3f3f;

int mp[][], ans[][];

int dx[] = {, , -, , , , -, -};

int dy[] = {, , , -, , -, , -};

int sum[][];

int sumr[];

int sumc[];

int get_cnt(int x, int y) {

    int cnt = ;

    for(int i = ; i < ; i++) {

        int nx = x + dx[i];

        int ny = y + dy[i];

        if(nx >  && nx <=  && ny >  && ny <=  && mp[nx][ny] == -) {

            cnt += ans[nx][ny];

        }

    }

    return cnt;

}

void add(int x, int y, int num) {

    for(int i = ; i < ; i++) {

        int nx = x + dx[i];

        int ny = y + dy[i];

        if(nx >  && nx <=  && ny >  && ny <=  && mp[nx][ny] != -) {

            sum[nx][ny] += num;

        }

    }

}

// bool check(int x, int y) {

//     if(mp[x - 1][y - 1] != -1) {

//         int cnt = get_cnt(x - 1, y - 1);

//         if(cnt != mp[x - 1][y - 1]) return false;

//     }

// }

bool check(int x, int y) {

    if(x !=  && y != ) {

        if(mp[x - ][y - ] != - && sum[x - ][y - ] != mp[x - ][y - ]) {

            return false;

        }

    }

    if(x ==  && y != ) {

        if(mp[x][y - ] != - && sum[x][y - ] != mp[x][y - ]) {

            return false;

        }

    }

    if(y ==  && x != ) {

        if(mp[x - ][y] != - && sum[x - ][y] != mp[x - ][y]) {

            return false;

        }

    }

    return true;

}

bool check_sum(int x, int y) {

    int num = ;

    for(int i = x + ; i <= ; i++) {

        if(mp[i][y] == -) {

            num++;

        }

    }

    if(num *  + sumc[y] <  || num + sumc[y] > ) {

        return false;

    }

    num = ;

    for(int i = y + ; i <= ; i++) {

        if(mp[x][i] == -) {

            num++;

        }

    }

    if(num *  + sumr[x] <  || num + sumr[x] > ) {

        return false;

    }

    if(!check(x, y)) {

        return false;

    }

    return true;

}

bool dfs(int x, int y) {

    if(x > ) return true;

    int tx = x, ty = y;

    ty++;

    if(ty > ) {

        ty = ;

        tx++;

    }

    if(mp[x][y] != -) {

        if(check(x, y) && dfs(tx, ty)) {

            return true;

        } else {

            return false;

        }

    }

    for(int num = ; num <= ; num++) {

        //debug1(num);

        ans[x][y] = num;

        sumr[x] += num;

        sumc[y] += num;

        add(x, y, num);

        if(check_sum(x, y) && dfs(tx, ty)) {

            return true;

        }

        sumr[x] -= num;

        sumc[y] -= num;

        add(x, y, -num);

    }

    return false;

}

int main() {

#ifndef ONLINE_JUDGE

    FIN

#endif

    int T;

    scanf("%d", &T);

    while(T--) {

        memset(mp, , sizeof(mp));

        memset(sum, , sizeof(sum));

        memset(ans, , sizeof(ans));

        memset(sumc, , sizeof(sumc));

        memset(sumr, , sizeof(sumr));

        int cas;

        scanf("%d", &cas);

        for(int i = ; i <= ; i++) {

            int cnt = ;

            for(int j = ; j <= ; j++) {

                scanf("%d", &mp[i][j]);

                if(mp[i][j] == -) cnt++;

                else ans[i][j] = mp[i][j];

            }

        }

        dfs(, );

        printf("%d\n", cas);

        for(int i = ; i <= ; i++) {

            for(int j = ; j <= ; j++) {

                printf("%d%c", ans[i][j], j ==  ? '\n' : ' ');

            }

        }

    }

    return ;

}

/**********************************************************************

    Problem: 2279

    User: buerdepepeqi

    Language: C++

    Result: AC

    Time:16 ms

    Memory:2024 kb

**********************************************************************/