蓝桥杯2018年第九届真题-整理玩具-题解（C++代码）详细注释

解题思路:    染色思想，深搜

    对于每个输入的图，全部交给chk函数判断是不是符合题目要求（标记相同整数的部件必须摆在一起，组成一个矩形形状）

    对于每个小矩形，判断这个范围内的玩具数量是不是等于全局中这个玩具的数量，并且等于这个范围的长 * 宽

注意事项:

参考代码:

#include <bits/stdc++.h>
using namespace std;

const int N = 15;
const int d[4][2] = { {1,0}, {0,-1}, {0,1}, {-1,0} };

char g[N][N]; //输入地图 
int ex, ey; //记录右下角 
int n, m;
int cnt[N]; //输入时每种玩具的实际数量 
int now[N]; //检查到的每种玩具有多少个 
int mark[N][N]; //染色 

//任务：记录小矩形右下角的坐标，记录每种玩具的数量，染色 
void dfs(int i, int j, int c) {
    ex = max(ex, i), ey = max(ey, j); //更新左下角的最大值 
    mark[i][j] = c; //染色 
	now[g[i][j] - '0'] ++; //i,j坐标上放的那种玩具 数量+1 
    for (int k = 0; k < 4; k ++) {
        int ni = i + d[k][0], nj = j + d[k][1]; //下一步的坐标 
        if ( (ni >= 0 && ni < n && nj >= 0 && nj < m )  &&  mark[ni][nj] == 0 && g[i][j] == g[ni][nj]) { //在地图内，没被染色，下一步的玩具和这一步一样 
            dfs(ni, nj, c); //继续染色 
        }
    }
}

// 
bool chk() { //检查整个地图 
    int color = 1; //色号 第几种颜色 
    for (int i = 0; i < n; i ++) //遍历整个地图 
    	for (int j = 0; j < m; j++) 
			if (mark[i][j] == 0) { //还没有遍历过 
		        ex = -1, ey = -1; //更新右下角的最大值 
		        dfs(i, j, color ++); //进行深搜 
		        if (now[g[i][j] - '0'] != cnt[g[i][j] - '0']) return false;//检查到的玩具的数量染成同一种颜色的格子数量等于该颜色的全局数量 
		        for (int ii = i; ii <= ex; ii ++) //枚举(ex-i) × (ey-j) 的矩形 
			        for (int jj = j; jj <= ey; jj ++) 
						if (mark[ii][jj] != mark[i][j]) //该颜色全局的数量且数量等于 (ex-i) × (ey-j)
			            	return false;
    	}
    return true;
}

int main() {
	std::ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    
    int T; cin >> T;
    
    while (T--) {
        cin >> n >> m;
        memset(cnt, 0, sizeof cnt), memset(now, 0, sizeof now), memset(mark, 0, sizeof mark); 
        for (int i = 0; i < n; i ++)
	        for (int j = 0; j < m; j ++) {
	            cin >> g[i][j];
	            cnt[g[i][j] - '0'] ++; //标记输入的地图 
	        }
        cout << (chk() ? "YES" : "NO") << '\n';
    }
    
    return 0;
}