首页 > 代码库 > SGU 168.Matrix
SGU 168.Matrix
时间限制: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;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。