欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

【2】Codeforces Global Round 9. B. Neighbor Grid

程序员文章站 2022-03-12 09:30:42
题目http://codeforces.com/contest/1375/problem/B思路当给定一个二维数组的时候,我们总是能够想办法构造出一个解法,除非某些值超过了限制(因为我们只能不断增加数值)。比如一个5 x 5 二维数组,它数值最大的解如下:2 3 3 3 23 4 4 4 33 4 4 4 33 4 4 4 32 3 3 3 2证明:首先,图中每个数值表示的是当前点的邻居数量,如果比该数量还大,则没有解。假如应该为4的点比4还要大,由于只有四个邻居,所以没有解。...

题目

http://codeforces.com/contest/1375/problem/B
【2】Codeforces Global Round 9. B. Neighbor Grid
【2】Codeforces Global Round 9. B. Neighbor Grid

思路

当给定一个二维数组的时候,我们总是能够想办法构造出一个解法,除非某些值超过了限制(因为我们只能不断增加数值)。
比如一个5 x 5 二维数组,它数值最大的解如下:
2 3 3 3 2
3 4 4 4 3
3 4 4 4 3
3 4 4 4 3
2 3 3 3 2
证明:
首先,图中每个数值表示的是当前点的邻居数量,如果比该数量还大,则没有解。

  • 假如应该为4的点比4还要大,由于只有四个邻居,所以没有解。
  • 假如应该为3的点比3还要大,由于3的点都在边缘,只有三个邻居,所以没有解。
  • 假如应该为2的点比2还要大,由于2的点都在角落,只有两个邻居,所有没有解。

其次,这确实是一个合法的解。

则得到解法:

  • 假如这个二位数组的每个点的初始数值都不超过这个解,那么我们总是可以通过增加数值的方式得到这个解。
  • 如果这个二位数组有的点的初始数值已经超过了这个解,那么我们无法得到一个解答。

代码

代码均为提交通过版本。为保持比赛时原样,没有后期优化或者修改。但为方便阅读,可能会增加注释。

#include <iostream>
using namespace std;
 
int main() {
	int tcase;
	std::ios::sync_with_stdio(false);
	cin >> tcase;
	while(tcase--) {
		int n, m;
		cin >> n >> m;
		bool answer = true;
		int v[302][302];
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < m; j++) {
				int x;
				cin >> x;
				if (!answer) {
					continue;
				}
				if (x > 4) {
					answer = false;
				} else if ((i == 0 && j == 0) || (i == 0 && j == m - 1 ) || (i == n - 1 && j == 0) || (i == n - 1 && j == m - 1)) { // 四个角落上的点
					if (x >= 3) {
						answer = false;
					} else {
						v[i][j] = 2;
					}
				} else if (i == 0 || j == 0 || i == n - 1 || j == m - 1) { // 除了四个角落外的边缘的点
					if (x >= 4) {
						answer = false;
					} else {
						v[i][j] = 3;
					}
				} else {
					v[i][j] = 4;
				}
			}
		}
		if (!answer) {
			cout << "NO" << endl;
		} else {
			cout << "YES" << endl;
			for(int i = 0; i < n; i++) {
				for(int j = 0; j < m; j++) {
					cout << v[i][j] <<" ";
				}
				cout << endl;
			}
		}
	}
	return 0;
}

本文地址:https://blog.csdn.net/rbb317/article/details/107138175