首页 > ACM题库 > HDU-杭电 > HDU 1218 Blurred Vision-模拟-[解题报告] C++
2013
12-04

HDU 1218 Blurred Vision-模拟-[解题报告] C++

Blurred Vision

问题描述 :

Aliasing is the stair-step effect achieved when attempting to represent a smooth curve using a finite number of discrete pixels. Of course, all computer displays consist of a finite number of pixels, and many strategies have been devised to smooth the jagged edges with varying degrees of success.

Boudreaux and Thibodeaux are writing video game rendering software for the next big first-person shooter, and they don’t know much about any of the progress made in the field of anti-aliasing. Therefore, they’ve decided to use a very simplistic (and visually unappealing) method to smooth the ragged edges. Unfortunately, it blurs the entire image, but at least it gets rid of those jaggies!

Normally, the game displays in m x n pixels, but they perform an extra anti-aliasing step that converts that image into an (m – 1) x (n – 1) image. Nobody will notice a pixel missing from each dimension, and they can calculate the new pixels by averaging squares of 4 pixels from the original image (and rounding down). For example, the images below represent the original image (left) and the anti-aliased image (right) using numbers to represent varying shades of black and white.
4 4 4 0
4 4 0 0
4 0 0 0
0 0 0 0

4 3 1
3 1 0
1 0 0

输入:

Input to this problem will consist of a (non-empty) series of up to 100 data sets. Each data set will be formatted according to the following description, and there will be no blank lines separating data sets.

A single data set has 3 components:

Start line – A single line:
START R C

where R and C are integers (2 ≤ (R,C) ≤ 9) indicating the number of rows and columns in the input image described by this data set.
Original Image – A series of R lines, each of which contains C integers from 0 to 9 inclusive. These integers represent the grayscale value of a pixel in the original image and will not be separated by spaces.
End line – A single line:
END

After the last data set, there will be a single line:

ENDOFINPUT

输出:

The output will be the anti-aliased image, which will be R – 1 rows, each with C – 1 integer pixel values. Each pixel in the output will be generated by averaging (and rounding down) the grayscale pixel values of the corresponding square of four pixels in the Original Image.

样例输入:

START 2 2
00
00
END
START 2 9
012345678
012345678
END
START 4 4
4440
4400
4000
0000
END
START 9 9
900000009
090000090
009000900
000909000
000090000
000909000
009000900
090000090
900000009
END
ENDOFINPUT

样例输出:

0
01234567
431
310
100
42000024
24200242
02422420
00244200
00244200
02422420
24200242
42000024

简单模拟,题意有点难懂,实际就是给你一个 r*c 的矩阵,让你转化为一个(r-1)*(c-1)的矩阵,新矩阵中每个点的值为以其左上角为起点的四节点小矩阵之和的平均值。

代码如下:

#include <cstdio>
#include <cstring>
int main()
{
    int r, c;
    char image[10][10], str[10];
    while(scanf("%s", str) && strcmp(str, "ENDOFINPUT"))
    {
        scanf("%d%d", &r, &c);
        int r1 = r-1, c1 = c-1;
        for(int i=0; i<r; i++)
            scanf("%s", image[i]);
        for(int i=0; i<r1; i++)
            for(int j=0; j<c1; j++)
                image[i][j] = (image[i][j]+image[i+1][j]+image[i][j+1]+image[i+1][j+1])/4;
        for(int i=0; i<r1; i++)
            image[i][c1] = 0;
        for(int i=0; i<r1; i++)
            printf("%s\n", image[i]);
        scanf("%s", str);//读取最后一个'END'
    }
    return 0;
}


  1. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。

  2. 题本身没错,但是HDOJ放题目的时候,前面有个题目解释了什么是XXX定律。
    这里直接放了这个题目,肯定没几个人明白是干啥

  3. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。

  4. 思路二可以用一个长度为k的队列来实现,入队后判断下队尾元素的next指针是否为空,若为空,则出队指针即为所求。