HDU 3359 Kind of a Blur

题目在这里>_<

题意

给出一个像素矩阵$A$,定义模糊后的矩阵$B$，$b_{ij}=\frac{1}{n}\sum\limits_{k=1}^n a_k$
其中$a_k$为到$a_{ij}$曼哈顿距离小于等于$t$的$A$中的值，$n$为其总个数。
现在给出模糊后的矩阵$B$和距离$t$,求出原矩阵$A$ 。

思路

$\frac{1}{n}\sum\limits_{k=1}^n a_k=b_{ij}$
$\sum\limits_{k=1}^n a_k=nb_{ij}$
由此得到了一个方程组，高斯消元求解即可。

代码

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <iostream>
#include <map>
#include <set>
//#define test
using namespace std;
const int Nmax=1e3+7;
typedef long long ll;

typedef double ld;
int n,m,t;
int dx[]={0,0,0,1,-1};
int dy[]={0,1,-1,0,0};
ld a[Nmax][Nmax];
ld ans[Nmax][Nmax];
int size;
void init()
{
    size=0;
    memset(ans,0,sizeof(ans));
}
void gaussJordan(int n,ld a[][Nmax])
{
    for(int i=1;i<=n;i++)
    {
        int idx=i;
        for(int j=i+1;j<=n;j++)
            if(fabs(a[idx][i])<fabs(a[j][i]))
                idx=j;
        if(idx!=i)
        {
            for(int j=i;j<=n+1;j++)
                swap(a[idx][j],a[i][j]);
        }
        for(int j=1;j<=n;j++)
        {
            if(j!=i)
            {
                ld t=a[j][i]/a[i][i];
                for(int k=i;k<=n+1;k++)
                    a[j][k]-=t*a[i][k];
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        a[i][n+1]/=a[i][i];
        a[i][i]=1.0;
    }
}
int id(int x,int y)
{
    return (x-1)*m+y;
}
void show()
{
    for(int i=1;i<=n*m;i++)
        for(int j=1;j<=n*m+1;j++)
            printf("%Lf%c",ans[i][j],j==n*m+1?'\n':' ');
}
int dis(int x,int y,int xx,int yy)
{
    return abs(xx-x)+abs(yy-y);
}
int main()
{
    #ifdef test
    #endif
    //freopen("i.in","r",stdin);
    int cases=0;
    while(~scanf("%d%d%d",&m,&n,&t))
    {
        cases++;
        if(!m && !n && !t)
            break;
        if(cases!=1)
            printf("\n");
        init();
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                scanf("%lf",&a[i][j]);
        for(int i=1;i<=n;i++) 
        {
            for(int j=1;j<=m;j++)
            {
                int times=0;
                ++size;
                //ans[size][id(i,j)]=1.0;
                for(int ii=1;ii<=n;ii++)
                {
                    for(int jj=1;jj<=m;jj++)
                    {
                        if(dis(i,j,ii,jj)<=t)
                        {
                            times++;
                            ans[size][id(ii,jj)]=1.0;

                        }
                    }
                }
                //for(int k=1;k<=4;k++)
                //{
                    //int nowx=i+dx[k],nowy=j+dy[k];
                    //if(nowx<1 || nowx>n || nowy<1 || nowy>m)
                        //continue;
                    //times++;
                    //ans[size][id(nowx,nowy)]=1.0;
                //}
                ans[size][n*m+1]=1.0*times*a[i][j];
            }
        }
    #ifdef test
        show();
    #endif
        gaussJordan(n*m,ans);
    #ifdef test
        printf("after:\n");
        show();
    #endif
        for(int i=1;i<=n*m;i++)
        {
            printf("%8.2lf",ans[i][n*m+1]);
            if(i%m==0)
                printf("\n");
        }
    }
    return 0;
}