题目大意：

4399上面的一个小游戏，突然想能不能用程序得到最优解。网址在这里大家可以去试着玩一玩：http://www.4399.com/flash/6356_2.htm

代码：

#include<iostream>
#include<math.h>
#include<stdio.h>
#include<string.h>
#include<queue>
#define maxn 10000000
using namespace std;

int map[10][10]={0};
//int x[10000],y[100000];
int n=0;
int last[maxn];//last[i]表示操作i的上一个操作的标号
int move[maxn][2];//操作i的+1位置。 
struct node
{
    int map[8][8];
    int x,y,n;
    int num;
};
queue<node>a;
node q,p;


bool empty(node x)
{
    for(int i=1;i<=6;i++)
    {
        for(int j=1;j<=6;j++)
        {
            if(x.map[i][j]!=0)return 0;
        }
    }
    return 1;
}
void output(node x)
{
    for(int i=1;i<=6;i++)
    {
        for(int j=1;j<=6;j++)
        {
            printf("%d ",x.map[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}

void boom(int x,int y)
{
    //cout<<x<<y<<endl;
    p.map[x][y]=0;
    int lx,ly;
    lx=x;ly=y;
    lx=x-1;
    while(1)
    {
        lx++;
        if(lx>6)break;
        if(p.map[lx][ly]!=0)
        {
            p.map[lx][ly]++;
            //cout<<p.map[lx][ly]<<endl;
            if(p.map[lx][ly]==5)
            {
                boom(lx,ly);
            }
            break;
        }
    }
    lx=x+1;
    while(1)
    {
        lx--;
        if(lx<1)break;
        if(p.map[lx][ly]!=0)
        {
            p.map[lx][ly]++;
            if(p.map[lx][ly]==5)
            {
                //cout<<"("<<lx<<","<<ly<<")"<<endl;
                boom(lx,ly);
            }
            break; 
        }
    }
    lx=x;ly=y-1;
    while(1)
    {
        ly++;
        if(ly>6)break;
        if(p.map[lx][ly]!=0)
        {
            p.map[lx][ly]++;
            if(p.map[lx][ly]==5)
            {
                boom(lx,ly);
            }
            break;
        }
    }
    ly=y+1;
    while(1)
    {
        ly--;
        if(ly<1)break;
        if(p.map[lx][ly]!=0)
        {
            p.map[lx][ly]++;
            if(p.map[lx][ly]==5)
            {
                boom(lx,ly);
            }
            break;
        }   
    }
}

void add(int x,int y)//p在点（x，y）加一个 
{
    p.map[x][y]++;
    p.n++;
    if(p.map[x][y]==5)
    {
        boom(x,y);
    }
}

void findway(int t)
{
    while(t!=0)
    {
        cout<<move[t][0]<<" "<<move[t][1]<<endl;
        t=last[t];
    }
}

void ceshi()
{
    for(int i=1;i<=6;i++)
    {
        for(int j=1;j<=6;j++)
        {
            cin>>p.map[i][j];
        }
    }
    cin>>n;
    while(n--)
    {
        int lx,ly;
        cin>>lx>>ly;
        add(lx,ly);
        for(int i=1;i<=6;i++)
        {
            for(int j=1;j<=6;j++)
            {
                cout<<p.map[i][j]<<" ";
            }
            cout<<endl;
        }
        cout<<endl;
    }
}
int main()
{
    int flag=0;
    //ceshi();
    while(1)
    {
        flag=0;
        n=0;
        for(int i=1;i<=6;i++)
        {
            for(int j=1;j<=6;j++)
            {
                cin>>map[i][j];
                if(map[i][j]!=0)n++;
            }
        }
        for(int i=1;i<=6;i++)
        {
            for(int j=1;j<=6;j++)
            {
                q.map[i][j]=map[i][j];
            }
        }
        q.num=0;
        q.n=0;
        a.push(q);
        while(!a.empty())
        {

            for(int i=1;i<=6;i++)
            {
                for(int j=1;j<=6;j++)
                {
                    if(a.front().map[i][j]==0)continue;
                    q=a.front();
                    p=q;
                    add(i,j);//给q这个状态在（i,j）点上+1
                    q=p;
                    //output(q);cout<<q.n<<endl;
                    q.num=n;
                    last[n]=a.front().num;
                    move[n][0]=i;move[n][1]=j;
                    n++;
                    a.push(q);
                    if(empty(q))
                    {
                        flag=1;
                        break;
                    }
                }
                if(flag==1)break;
            }
            if(flag==1)
            {
                cout<<q.n<<endl;
                findway(n-1);
                break;
            }
            a.pop();
        }


    }
}

几组测试样例：

输入：
3 0 0 0 4 0
0 0 0 0 4 0
0 0 0 0 0 0
0 0 4 0 1 0
0 0 0 0 0 0
0 0 0 0 0 0
输出：
4
1 1
2 5
4 3
4 5

输入：
3 0 1 2 0 3
4 1 0 3 1 2
2 2 2 4 3 3
0 4 3 3 2 3
2 0 1 0 3 4
2 1 4 3 2 1
4
1 6
2 4
4 3
3 4

实际游戏出现情况：
第一关：
3 3 1 1 3 2
2 0 3 0 3 3
4 4 2 2 3 3
0 0 4 3 0 4
4 2 0 1 2 3
1 2 2 2 2 1

第二关：
2 2 2 4 1 3
0 3 4 2 4 1
3 1 3 3 0 3
3 2 3 2 0 0
4 3 4 0 1 3
2 0 4 0 2 2

第三关：（程序出错）
1 2 3 0 2 4
4 0 2 2 2 3
0 0 3 2 4 1
4 0 0 2 3 0
3 3 0 3 0 4
0 3 3 2 2 1

第一关： (出错)
3 1 2 1 1 2
1 1 4 3 4 4
2 0 3 0 2 2
1 4 2 4 0 3
3 3 1 1 3 2
2 2 0 3 0 0
本样例，手动将（4,2）+1后，跑出来是4次，一共五次
将maxn变为1e7后成功跑出，原来是内存不够。

第二关：还是跑不出来
2 0 4 2 4 3
0 1 1 2 2 4
3 2 1 1 3 3
2 3 0 0 1 3
2 3 0 3 3 2
3 4 4 4 0 0
我就吧maxn变成1e8了，然后电脑就蓝屏了，大概是爆内存了。

根据以上程序及样例数据，大概能加5滴水是极限，再继续跑内存就存不下数据了，而且就该太慢了。有时间要先办法重新优化一下。不过确实神奇，有的样例在把前三个点下去的时候都还没什么变化，直到点下最后一个，然后瞬间爆炸全清，这个爽啊~

优化思路：

1.存图方面，因为可能存的值只有0-5，所以想办法用位运算优化。
2.搜索结点访问方面，先办法在减少一些访问，比如一个1的点，要加4滴水，这四滴水都可以给周围4个点每个点都加一遍了，当然这并不能说明给这个1点的加就一定不会是最优，具体优化方法还有仔细证明。
3.保存路径方面也是有同样的所占内存太大的问题。
注：上面程序输出的加水位置是倒序输出的。

目标：100关！

未完待续。。。。