首页 > 代码库 > HDU 3359 Kind of a Blur(高斯消元)
HDU 3359 Kind of a Blur(高斯消元)
题意:
H * W (W,H <= 10) 的矩阵A的某个元素A[i][j],从它出发到其他点的曼哈顿距离小于等于D的所有值的和S[i][j]除上可达点的数目,构成了矩阵B。给定矩阵B,求矩阵A。
题目先给宽再给高。。。坑我了一个小时
code
/* 暴力确定每个位置有到那些位置的曼哈顿距离小于D 然后对你n*m个未知数,n*m个方程进行高斯消元*/#include <iostream>#include <cstdio>#include <cmath>#include <cstring>using namespace std;const int MAXN = 111;int n, m, dx, cnt;double A[MAXN][MAXN], ans[MAXN];inline void build (int x, int y, int d) { int k = 0; for (int i = 0, tol = 0; i < n; ++i) for (int j = 0; j < m; ++j) { if (abs (i - x) + abs (j - y) <= dx) A[d][tol++] = 1, ++k; else A[d][tol++] = 0; } A[d][cnt] *= k;}void Gauss() { int i, j, k; double tmp, big; for (i = 0; i < cnt; i++) { for (big = 0, j = i; j < cnt; j++) { if (abs (A[j][i]) > big) { big = abs (A[j][i]); k = j; } } if (k != i) { for (j = 0; j <= cnt; j++) swap (A[i][j], A[k][j]); } for (j = i + 1; j < cnt; j++) { if (A[j][i]) { tmp = -A[j][i] / A[i][i]; for (k = i; k <= cnt; k++) A[j][k] += tmp * A[i][k]; } } } for (i = cnt - 1; i >= 0; i--) { tmp = 0; for (j = i + 1; j < cnt; j++) tmp += A[i][j] * ans[j]; ans[i] = (A[i][j] - tmp) / A[i][i]; }}int main() { int cs = 0; while (scanf ("%d %d %d", &m, &n, &dx), n) { if (cs == 0) cs = 1; else putchar (10); cnt = n * m; for (int i = 0, tol = 0; i < n; ++i) for (int j = 0; j < m; ++j) scanf ("%lf", &A[tol++][cnt]); for (int i = 0, tol = 0; i < n; ++i) for (int j = 0; j < m; ++j, ++tol) build (i, j, tol); Gauss (); for (int i = 0, cnt = 0; i < n; i++) { for (int j = 0; j < m; j++) printf ("%8.2f", ans[cnt++]); putchar (10); } } return 0;}
HDU 3359 Kind of a Blur(高斯消元)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。