自动搬运

查看原文

来自洛谷，原作者为

	zhang_Jimmy Geography Monitor.

搬运于2025-08-24 21:15:31，当前版本为作者最后更新于2023-09-26 18:31:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

我们可以另外定义一个 $f$ 数组，$f_{i,j}$ 表示以第 $i$ 行第 $j$ 列格子为底的悬线的长度。

如果 $a_{i,j}$ 是质数，那么就从 $a_{i-1,j}$ 上的悬线长度延伸过来，也就是 $f_{i,j}=f_{i-1,j} + 1$。

如果 $a_{i,j}$ 不是质数，那么 $f_{i,j} = 0$。

代码如下：

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

int t, n, m, a[210][210], f[210][210];

bool prime(int n){
	if(n == 1) return 0;
	if(n == 2) return 1;
	for(int i = 2; i <= sqrt(n); i ++)
		if(n % i == 0) return 0;
	return 1;
}

int main(){
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	cin >> t;
	while(t --){
		memset(f, 0, sizeof f);
		cin >> n >> m;
		for(int i = 1; i <= n; i ++){
			for(int j = 1; j <= m; j ++){
				cin >> a[i][j];
			}
		}
		for(int i = 1; i <= n; i ++){
			for(int j = 1; j <= m; j ++){
				if(prime(a[i][j]))
					f[i][j] = f[i - 1][j] + 1;
				else 
					f[i][j] = 0;
			}
		}
		for(int i = 1; i <= n; i ++){
			for(int j = 1; j <= m; j ++){
				cout << f[i][j] << " ";
			}
			cout << endl;
		}
	}
	return 0;
}