首页 > ACM题库 > HDU-杭电 > HDU 3359-Kind of a Blur-数论-[解题报告]HOJ
2014
03-16

HDU 3359-Kind of a Blur-数论-[解题报告]HOJ

Kind of a Blur

问题描述 :

Image blurring occurs when the object being captured is out of the camera’s focus. The top two figures on the right are an example of an image and its blurred version. Restoring the original image given only the blurred version is one of the most interesting topics in image processing. This process is called deblurring, which will be your task for this problem.
In this problem, all images are in grey-scale (no colours). Images are represented as a 2 dimensional matrix of real numbers, where each cell corresponds to the brightness of the corresponding pixel. Although not mathematically accurate, one way to describe a blurred image is through averaging all the pixels that are within (less than or equal to) a certain Manhattan distance?from each pixel (including the pixel itself ). Here’s an example of how to calculate the blurring of a 3×3 image with a blurring distance of 1:
Land Division

Given the blurred version of an image, we are interested in reconstructing the original version assuming that the image was blurred as explained above.

Land DivisionLand DivisionLand Division

输入:

Input consists of several test cases. Each case is specified on H + 1 lines. The first line specifies three non negative integers specifying the width W, the height H of the blurred image and the blurring distance D respectively where (1<= W,H <= 10) and (D <= min(W/2,H/2)). The remaining H lines specify the gray-level of each pixel in the blurred image. Each line specifies W non-negative real numbers given up to the 2nd decimal place. The value of all the given real numbers will be less than 100.
Zero or more lines (made entirely of white spaces) may appear between cases. The last line of the input file consists of three zeros.

输出:

Input consists of several test cases. Each case is specified on H + 1 lines. The first line specifies three non negative integers specifying the width W, the height H of the blurred image and the blurring distance D respectively where (1<= W,H <= 10) and (D <= min(W/2,H/2)). The remaining H lines specify the gray-level of each pixel in the blurred image. Each line specifies W non-negative real numbers given up to the 2nd decimal place. The value of all the given real numbers will be less than 100.
Zero or more lines (made entirely of white spaces) may appear between cases. The last line of the input file consists of three zeros.

样例输入:

2 2 1
1 1
1 1

3 3 1
19 14 20
12 15 18
13 14 16

4 4 2
14 15 14 15
14 15 14 15
14 15 14 15
14 15 14 15

0 0 0

样例输出:

    1.00    1.00
    1.00    1.00

    2.00   30.00   17.00
   25.00    7.00   13.00
   14.00    0.00   35.00

    1.00   27.00    2.00   28.00
   21.00   12.00   17.00    8.00
   21.00   12.00   17.00    8.00
    1.00   27.00    2.00   28.00
Hint
The Manhattan Distance (sometimes called the Taxicab distance) between two points is the sum of the (absolute) difference of their coordinates. The grid on the lower right illustrates the Manhattan distances from the grayed cell.

HDU 3359    http://acm.hdu.edu.cn/showproblem.php?pid=3359

高斯消元基础题   模板题吧

参考黑书上的代码写的

#include<stdio.h>
#include<iostream>
#include<string>
#include<stdlib.h>
#include<string.h>
#include<math.h>
using namespace std;
typedef double Matrix[105][105];

int mht(int i,int j,int m,int n){
    return abs(i-m)+abs(j-n);    
}

void gauss(Matrix A ,int n){
    int i,j,k,r;
    
    for(i = 0; i < n; i++){
        r = i;
        for(j = i+1; j < n; j++){
            if( fabs(A[j][i]) > fabs(A[r][i]) )  r = j;
        }
        if(r != i) for(j = 0; j <= n; j++) swap(A[r][j],A[i][j]); 
        
        
        for(k = i+1; k < n; k++){
            double f = A[k][i] / A[i][i];
            for(j = i; j <= n; j++)  A[k][j] -= f * A[i][j];
        }
        
        /*
        for(j = n; j >= i; j--){
            for(k = i+1; k < n; ++k)
                A[k][j] -= A[k][i]/A[i][i] * A[i][j];
        }
        */
    }
    for(i = n-1; i >= 0; --i ){
        for(j = i+1; j < n; ++j)
            A[i][n] -= A[j][n] * A[i][j];
        A[i][n] /= A[i][i];
    }
    
}

int main(){

//    freopen("in.txt","r",stdin); 

 //   freopen("out.txt","w",stdout); 
    Matrix g;
    double map[12][12];
    int pos[120][120];
    int r,c,d;
    bool is_first=true;
    while(scanf("%d%d%d",&c,&r,&d),r||c||d){
        if(!is_first)
            printf("\n");
        is_first=false;
        int i,j;
        int cnt=0;
        for(i=0;i<r;i++){
            for(j=0;j<c;j++){
                pos[i][j]=cnt++;
                scanf("%lf",&map[i][j]);
            }
        }
        memset(g,0,sizeof(g));
        int m,n;
        for(i=0;i<r;i++){
            for(j=0;j<c;j++){
                for(m=0;m<r;m++){
                    for(n=0;n<c;n++){
                        if( mht(i,j,m,n)<=d ){
                            g[ pos[i][j] ][ pos[m][n] ]=1;
                            g[ pos[i][j] ][cnt] += map[i][j];
                        }
                    }
                }
            }
        }
        

        gauss(g,cnt);
        
        for(i=0;i<cnt;i++){
            printf("%8.2lf",g[i][cnt]);
            if( (i+1)%c == 0 )
                putchar(10);
        }
    }
    return 0;
}

参考:http://blog.csdn.net/u010724594/article/details/18262155


  1. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?