# 题面易守难攻

袋鼠将军需要选择若干个地形制高点作为驻地。整个平原被划分为一个 n 行 m 列的网格，每个格子上都有一个高度值。我们称格子 (x,y) 其中 1≤x≤n,1≤y≤m 为 驻地点，当且仅当它满足以下两个条件：

该格子不位于边界上，即 1<x<n 且 1<y<m 。
该格子的高度值 严格大于 其 8 个相邻格子的高度值。与 (x,y)(x,y) 相邻的格子包括：
(x−1,y−1), (x−1,y), (x−1,y+1), (x,y−1), (x,y+1), (x+1,y−1), (x+1,y), (x+1,y+1)

现在，袋鼠将军可以任意重新分配格子的高度值。它可以将整数 1,2,…,n×m 各放入一个格子中使其成为对应格子的高度值，且使得每个数恰好出现一次。

你需要给出一组高度值的分配方案，使得 驻地点 的个数等于指定的值；或者报告不存在这样的分配方案。

# 输入格式

输入包含多组数据。

首先输入一行一个整数 T (1≤T≤ $10^4$ )，表示数据的组数。

对于每组数据，输入一行三个整数 n, m, k (1≤n≤100, 1≤m≤100, 0≤k≤n×m)，表示整个平原被划分为了 n 行 m 列的网格，且 驻地点 的个数需要为 k。

保证对于一个测试点的所有数据，n×m的和不超过 $10^6$ 。

# 输出格式

对于每组数据：

如果存在合法的分配方案，使得 驻地点 的个数等于指定的值，首先输出一行一个字符串 "Yes"，然后输出 n 行，每行 m 个整数，表示划分的方案。如果存在多组合法的分配方案，输出一组即可。
如果不存在合法的分配方案，输出一行一个字符串 "No"。

注意： 输出对大小写不敏感。例如，"YES" 与 "yEs" 都可以表示存在合法的分配方案。

# 样例

输入数据1

输出数据1

Yes 
4 3 5 
7 9 1 
2 8 6 
Yes
2 17 16 4 3 
15 18 14 13 
12 11 10 9 19
8 20 1 7 6 5 
No 
Yes 
2 1

# 提示

在第一组数据中，有且仅有位于 (2,2) 的 9 大于相邻的所有高度值。

在第二组数据中，位于 (2,2) 的 18 与位于 (3,4)的 19 大于相邻的所有高度值。

在第三组数据中，不存在合法的分配方案。

在第四组数据中，可以被选择为驻地点的格子的数量为 0。

# 思路

我先吐槽一下这个傻逼 devc++ 开二维数组的时候vector<vector<int**>>** 这个>>必须要加空格不然会报错
我比赛的时候还以为是自己太久没写题二维动态数组不会开了不然这题能a的
OK啊下面开始写题解思路
其实很简单能想到最能物尽其用的驻地方法即将从大到小的k个数隔一行（列）部署
一定一定不要让这些数有相邻部分
即可以按(2,2)(2,4)(2,6)(4,2)...... 的方式部署

其他	驻地	其他
1	2	3
4	9	5
6	7	8

3 * 3 如上图
于是便知道只要计算出一共能部署多少格与k做比较
然后输出Yes的部分先从大到小部署k个之后剩余部分从1到 n * m - k 部署就行
代码如下

#include <bits/stdc++.h>
#define int long long 
using namespace std ;
int solve () {
  int n , m  , k ;
  cin >> n >> m >> k ;
  int mx = ((n - 1)/2)*((m-1)/2) ;
  if ( mx < k ) {
    cout << "NO" << '\n' ;
    return 0 ;
  }
  else {
    vector<vector<int>> area(n + 1 , vector<int>(m + 1 , 0) ) ;
    int cnt = 0 ;
    int in = 1;
    for (int i = 2; i < n && cnt < k ; i += 2 ){
      for (int j = 2 ; j < m && cnt < k; j += 2 ){
        area[i][j] = (n * m - cnt ) ;
        cnt ++ ;
      }
    }
    for (int i = 1; i <= n ; i ++ ) {
      for (int j = 1 ; j <= m ; j ++ ) {
        if (area[i][j] == 0 ) {
        area[i][j] = in ;    
        in ++ ;
        }
      }
    }
    cout << "Yes" << '\n' ;
    for (int i = 1; i <= n ; i ++ ) {
      for (int j = 1 ; j <= m ; j ++ ) {
        cout << area[i][j] << " " ;
      }
      cout << '\n' ;
    }
   }
}
signed main () {
  ios::sync_with_stdio(0) ;
  cin.tie(0) ;
  int _ ;
  cin >> _ ;
  while (_-- ){
    solve () ;
  }
}

ACM

# 题面 易守难攻