首页 > 代码库 > HDU3359 Kind of a Blur(高斯消元)

HDU3359 Kind of a Blur(高斯消元)

建立方程后消元

 

#include<cstdio>#include<iostream>#include<cstdlib>#include<cstring>#include<string>#include<algorithm>#include<map>#include<queue>#include<vector>#include<cmath>#include<utility>using namespace std;typedef long long LL;const int N = 108, INF = 0x3F3F3F3F;const double eps = 1e-8;double f[N][N];bool inf[N];template<typename T>void gauss_jordan(T A[N][N], int n){    for(int i = 0; i < n; i++){        //选择一行r与第i行交换        int r = i;        for(int j = i + 1; j < n; j++){            if(abs(A[j][i]) > abs(A[r][i])){                r = j;            }        }        if(abs(A[r][i]) < eps){            continue;        }        if(r != i){            for(int j = 0; j <= n; j++){                swap(A[r][j], A[i][j]);            }        }        for(int k = 0; k < n; k++){            if(k != i){                for(int j = n; j >= i; j--){                    A[k][j] -=  A[k][i] / A[i][i] * A[i][j];                }            }        }    }}int main(){    bool flag = 0;    int h, w, d;    while(scanf("%d %d %d", &w, &h, &d), w || h || d){        memset(f, 0, sizeof(f));        for(int i = 0; i < h; i++){            for(int j = 0; j < w; j++){                double t;                scanf("%lf", &t);                int u = i * w + j;                f[u][w * h] = t;                int cnt = 0;                for(int x = max(0, i - d) ; x <= min(h - 1, i + d); x++){                    for(int y = max(0, j - d) ; y <= min(w - 1, j + d); y++){                        if(abs(x - i) + abs(y - j) <= d){                            cnt ++;                        }                    }                }                for(int x = max(0, i - d) ; x <= min(h - 1, i + d); x++){                    for(int y = max(0, j - d) ; y <= min(w - 1, j + d); y++){                        if(abs(x - i) + abs(y - j) <= d){                            int v = x * w + y;                            f[u][v] = 1.0 / (double)cnt;                        }                    }                }            }        }        gauss_jordan(f, w * h);        if(flag){            printf("\n");        }        flag = 1;        for(int i = 0; i < h; i++){            for(int j = 0; j < w; j++){                printf("%8.2f", f[i * w + j][w * h] / f[i * w + j][i * w + j]);            }            printf("\n");        }    }    return 0;}

  

HDU3359 Kind of a Blur(高斯消元)