传送门：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("********* ") #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)<<"] " #define debug2(x,y) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<"] " #define debug3(x,y,z) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<" "<<#z<<" "<<z<<"] " LL read() { int x = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-')f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } const double eps = 1e-8; const int mod = 1e9 + 7; const int maxn = 3e5 + 5; const int INF = 0x3f3f3f3f; const LL INFLL = 0x3f3f3f3f3f3f3f3f; int mp[15][15], ans[15][15]; int dx[] = {1, 0, -1, 0, 1, 1, -1, -1}; int dy[] = {0, 1, 0, -1, 1, -1, 1, -1}; int sum[15][15]; int sumr[15]; int sumc[15]; int get_cnt(int x, int y) { int cnt = 0; for(int i = 0; i < 8; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if(nx > 0 && nx <= 10 && ny > 0 && ny <= 10 && mp[nx][ny] == -1) { cnt += ans[nx][ny]; } } return cnt; } void add(int x, int y, int num) { for(int i = 0; i < 8; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if(nx > 0 && nx <= 10 && ny > 0 && ny <= 10 && mp[nx][ny] != -1) { 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 != 1 && y != 1) { if(mp[x - 1][y - 1] != -1 && sum[x - 1][y - 1] != mp[x - 1][y - 1]) { return false; } } if(x == 10 && y != 1) { if(mp[x][y - 1] != -1 && sum[x][y - 1] != mp[x][y - 1]) { return false; } } if(y == 10 && x != 1) { if(mp[x - 1][y] != -1 && sum[x - 1][y] != mp[x - 1][y]) { return false; } } return true; } bool check_sum(int x, int y) { int num = 0; for(int i = x + 1; i <= 10; i++) { if(mp[i][y] == -1) { num++; } } if(num * 3 + sumc[y] < 10 || num + sumc[y] > 10) { return false; } num = 0; for(int i = y + 1; i <= 10; i++) { if(mp[x][i] == -1) { num++; } } if(num * 3 + sumr[x] < 10 || num + sumr[x] > 10) { return false; } if(!check(x, y)) { return false; } return true; } bool dfs(int x, int y) { if(x > 10) return true; int tx = x, ty = y; ty++; if(ty > 10) { ty = 1; tx++; } if(mp[x][y] != -1) { if(check(x, y) && dfs(tx, ty)) { return true; } else { return false; } } for(int num = 1; num <= 3; 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, 0, sizeof(mp)); memset(sum, 0, sizeof(sum)); memset(ans, 0, sizeof(ans)); memset(sumc, 0, sizeof(sumc)); memset(sumr, 0, sizeof(sumr)); int cas; scanf("%d", &cas); for(int i = 1; i <= 10; i++) { int cnt = 0; for(int j = 1; j <= 10; j++) { scanf("%d", &mp[i][j]); if(mp[i][j] == -1) cnt++; else ans[i][j] = mp[i][j]; } } dfs(1, 1); printf("%d ", cas); for(int i = 1; i <= 10; i++) { for(int j = 1; j <= 10; j++) { printf("%d%c", ans[i][j], j == 10 ? ' ' : ' '); } } } return 0; } /********************************************************************** Problem: 2279 User: buerdepepeqi Language: C++ Result: AC Time:16 ms Memory:2024 kb **********************************************************************/