【2】Codeforces Global Round 9. B. Neighbor Grid
程序员文章站
2022-06-21 19:19:28
题目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
思路
当给定一个二维数组的时候,我们总是能够想办法构造出一个解法,除非某些值超过了限制(因为我们只能不断增加数值)。
比如一个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