首页 > 代码库 > 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;}
View Code

 

HDU 3359 Kind of a Blur(高斯消元)