首页 > 代码库 > SGU 168.Matrix

SGU 168.Matrix

2024-07-17 17:33:20   223人阅读

时间限制：0.5s

空间限制：15M

题意：

      给出一个N*M的矩阵A，计算矩阵B，满足B[i][j]=min{ A[x][y]:(y>=j) and ( x>=i+j-y )}

 

 

 

 

 

 

Solution : 

             

              如图方式从右下角遍历矩阵，那么可令B[i][j]=min(A[i][j],B[i-1][j],B[i][j+1],B[i-1][j+1])

              动态规划即可。

              时间复杂度O（n*m)

 

code

#include <iostream>#include <cstring>#include <cstdio>using namespace std;int A[1009][1009], B[1009][1009];int n, m;int main() {	scanf ("%d %d", &n, &m);	memset (B, 0x3f, sizeof B);	for (int i = 1; i <= n; i++)		for (int j = 1; j <= m; j++) scanf ("%d", &A[i][j]);	int x = n, y = m, i = n, j = m;	while (x >= 1 || y >= 1) {		while (i <= n && j >= 1) {			B[i][j]  = min (min (A[i][j], B[i][j + 1]), min (B[i + 1][j], B[i - 1][j + 1]) );			i++, j--;		}		if (i > n || j < 1) {			i = --x, j = y;			if (i <= 0) i = 1, j = --y;		}	}	for (int i = 1; i <= n; i++) {		for (int j = 1; j <= m; j++)			printf ("%d ", B[i][j]);		putchar (10);	}	return 0;}

　　

　　


联系
我们