残阳似血的博客

在计算机图形学发展史中，真实感绘制一直是主旋律。不过从20实际90年代中期开始，非真实感图像绘制(Non-Photorealistic Rendering，NPR）逐渐成为一个研究热点。说白了，真实感绘制目标是像照片般真实地再现客观世界，而非真实感图像绘制专注于图形个性化和艺术化的表达，它主要用来表现图形的艺术特质，以及模拟艺术作品（甚至包括作品中的缺陷）。

在介绍完非真实感图像绘制之后，我们再来提及一下PIL——Python Imaging Library（官方网址）。相信使用python的朋友们都不会陌生，因为在web应用中我们常常用它来生成缩略图。从名字也可以看出，PIL主要用来处理图片，它支持多种图片格式，并提供强大的图片和图像处理能力。详细的关于PIL的内容大家可以参阅手册。

这个系列，我们就主要使用PIL来进行滤镜方面的处理，包括素描、铅笔画、油画等等滤镜效果的实现。在以后我会把代码托管出来。

PIL已经内置一些滤镜效果，详细见文档和这篇文章。

声明：这篇文章中涉及的游戏来自@陈荣峰ayuLemon的创意，文章的主要目的还是研究这个游戏其中的算法，我所写的网页版的游戏版本也仅仅是为了验证算法的正确性。说明这个是防止大家误认游戏乃我的原创。本来原作者要求我不能在他的算法出来之前发出此文，我百思不得其解。我认为这个没有先后顺序，思前想后，还是发出来了。仅讨论之用。

事情的起因是这样的，在我又度过了一个不眠之夜、正打算睡觉之时，看到@python4cn 转发了一个同学的微博，原文是这样的：

@陈荣峰ayuLemon：用python做了个小游戏，这是5*5方格。每点击上面的方格一次，就改变周围四个方格和被点击方格的颜色，对于任意n*n方格，可否通过若干次点击使方格的颜色与最初完全相反？？（3*3和4*4的都很容易~~这个5*5的似乎有困难） 大家帮忙想一想，证明行或者不行，哪些行，哪些不行~~

本来已经很困的我看到这个，又勾起了我的好奇。于是拿起纸笔，开始演算。当然首先从2×2开始，一直到4×4，确实没有什么困难。到5×5，算了很久才算出一个结果。

在分析这个问题之前，如果你想试玩，我做了一个网页版的，地址在这里。

相信大家都用过微博，我们在微博的timeline中，常常可以看到文字、音乐、视频等等的混合。所有的内容都聚合在一起显示出来。具体的实现未可知，但是在Django中，我们有比较优雅的方式。那就是使用contenttypes模块来实现。

现在我们假设对于一条微博只有三种方式（其他的很容易拓展）：文本，音乐以及视频。我们先定义三个简单的Model。（注意到Music和Video只要简单继承Tweet类即可。）

from django.db import models
from django.contrib.auth.models import User

class Tweet(models.Model):
    user = models.ForeignKey(User) # 这里就用Django自带的User
    content = models.CharField(max_length=140) # 内容，最多140字
    pic_url = models.URLField(null=True, blank=True)
    created = models.DateTimeField(auto_now_add=True)
    
    class Meta:
        ordering = ['-created',]
        
    def __unicode__(self):
        return self.content
    
class Music(Tweet):
    music_url = models.URLField(verify_exists=False)
    
class Video(Tweet):
    video_url = models.URLField(verify_exists=False)

我们的网站通常都要集成搜索服务。通常情况下，我们都使用自己的搜索后端，例如使用Django，对于Python，我们主要有两种选择，一种是Whoosh，它是纯Python写成的搜索后端；另一种则是著名的Lucene的Python扩展，PyLucene，要提醒使用PyLucene，需要安装JVM。以后的文章我会介绍他们。

不过，今天的主角显然不是它们。因为有时候，我们并不需要这么麻烦，有时我们只需要集成一个Google搜索在其中就可以了。那么，Google custom search就派上了用场。在这里，我们也有三种方案：

1. 用iframe版本的cse，使用这种方式，甚至不需要写什么代码。
2. 使用Google ajax API，使用ajax方式获取搜索结果，然后用js将结果呈现在页面上。
3. 使用Custom search API，在后端使用Python的http编程，远程获取json方式的结果，并把数据渲染到模板中。

在一切开始之前，必须先创建一个新的自定义搜索。在cse页面上，点击“Create a Custom Search Engine”，如果已经新建过了，点击下面的“manage your existing search engines”。

今天讨论超能饮料的问题。这里是题目的来源。这个超能饮料的题目，颇有些炒作的嫌疑。据说这道题是程序员百万年薪招聘的题目之一。今天也是无意中从同学那里知道，这里就简单给出思路，然后给出Python语言的实现版本。

这里简单说一下超能饮料问题的大意。现在，已知有若干种原料，它们以C开头，比如：C1、C2.......一种原料转化为另一种原料需要使用定制的机器，而这也是成本主要来源（原料成本不计）。机器标记以M开头，如：M1、M2......

现在我们有一系列的输入（命令行参数形式，给出文件名，以文件形式读入），文件的每一行都代表特定的设备型号。每一行的格式如下：

<machine name>  <orig compound>  <new compound>  <price>（分别对应的中文意思是设备名称、源化合物、新化合物、价格）

输入文件示例：

M1  C1  C2  277317
M2  C2  C1  26247
M3  C1  C3  478726
M4  C3  C1  930382
M5  C2  C3  370287
M6  C3  C2  112344

题目的要求是，求无论能买到那种原料，都保证能生产出其他原料，并且保证花费的代价最小。

要求返回值的格式为：第一行，最优总价格。第二行，机器列表（去掉开头M），比如上例的输出示例：

617317
2 3 6

读完这条题目，我们可以发现，这题目其实是一条典型的图论题。对于某一个状态Ci，我们可以通过Mk转移至Cj，权重为Wm。于是，根据题意，我们实际上要求的是这样一条或者多条环路，使得它们包含所有的原料，并且，环路上所有的权重和最小。

在此基础上，我们必须满足两点。

1. 这条环路必须包含所有的原料。如果不能满足包含全部原料，就不能保证“无论能买到哪种原料，都保证能生产出其他原料”的条件。
2. 对于重复出现的状态转移，只需计算一遍。

综上所述，问题要解决的在已知图中求一条或多条环路，并且使这些环路中包含所有原料。