No Prime Differences

题面翻译

$n \times m$ 的网格，填入 $1,2,3,...,n \times m$，使得相邻的两个方格的差不是质数。

多组数据，输出任意一种方案（保证有解），每组输出间有空行（见样例）。

题目描述

You are given integers $ n $ and $ m $ . Fill an $ n $ by $ m $ grid with the integers $ 1 $ through $ n\cdot m $ , in such a way that for any two adjacent cells in the grid, the absolute difference of the values in those cells is not a prime number. Two cells in the grid are considered adjacent if they share a side.

输入格式

The first line of the input contains a single integer $ t $ ( $ 1 \le t \le 1000 $ ) — the number of test cases. The description of the test cases follows.

The first and only line of each test case contains two integers $ n $ and $ m $ ( $ 4 \le n, m \le 1000 $ ) — the dimensions of the grid.

It is guaranteed that the sum of $ n\cdot m $ over all test cases does not exceed $ 10^6 $ .

输出格式

For each test case, output $ n $ lines of $ m $ integers each, representing the final grid. Every number from $ 1 $ to $ n\cdot m $ should appear exactly once in the grid.

The extra spaces and blank lines in the sample output below are only present to make the output easier to read, and are not required.

If there are multiple solutions, print any of them.

样例 #1

样例输入 #1

样例输出 #1

16  7  1  9
12  8  2  3
13  4 10 11
14  5  6 15

29 23 17  9  5  6  2
33 27 21 15 11  7  1
32 31 25 19 20 16 10
26 30 24 18 14  8  4
35 34 28 22 13 12  3

 2  3  7 11
 8  9  1 10
17 13  5  4
18 14  6 12
19 23 15 21
20 24 16 22

分析

构建一个 n\times m 的矩阵

首先, 首先首先, 1不是素数, 所以我们可以构建出以下这个矩阵

$\begin{matrix} &1 &2 &3 &4 \\ &5 &6 &7 &8 \\ &9 &10 &11 &12\\ \end{matrix}$

这样子横向差都是1, 但是这样纵向差是 $m$, 如果 $m$ 是素数, 那这样子就寄了

那我们又想, 纵向差是 $m$ 不可以, 那么如果差是 $2\times m$ 不就可以了吗, 所以我们完全可以先按以上方法构造, 然后把奇数行凑一起输出, 把偶数行凑一起输出

有一点要注意的是, 先输出偶数行, 再输出奇数行, 可以避免出现纵向差为 $m$ 的情况, 如果先输出奇数行, 可能会出现第一行, 第三行, 第二行, 第四行的情况, 还是有可能出现纵向差是 $m$

代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int a[N][N];

int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	int t; cin >> t;
	while(t--)
	{
		int n, m; cin >> n >> m;
		int num = 1;
		for(int i = 1; i <= n; i++)
			for(int j = 1; j <= m; j++)
				a[i][j] = num++;
		
		//先输出偶数行 
		for(int i = 2; i <= n; i += 2)
		{
			for(int j = 1; j <= m; j++)
				cout << a[i][j] << ' ';
			cout << endl;	
		} 
		//再输出奇数行
		for(int i = 1; i <= n; i += 2)
		{
			for(int j = 1; j <= m; j++)
				cout << a[i][j] << ' ';
			cout << endl;
		}
		cout << endl;
	}
}

JZTXT

CF1838C