相邻方案

Description

有一个5*5的矩阵，每个元素只可能是H或者J。

我们现在需要选择7个相邻的格子使得H的数量小于J的数量。其中，拥有公共边的两个格子可以被称为相邻的格子。

对于任意一种输入的5*5矩阵，请输出满足上述条件的方案总数。

Input Format

共5行，表示矩阵情况。（每一个元素只可能是H或J）

Output Format

一个整数N，代表不相同方案的总数。

Input Sample

HHHHH JHJHJ HHHHH HJHHJ HHHHH

Output Sample

2 原题是USACO 2005 2月 数据在此:http://contest.usaco.org/FEB05_9.htm 数据乃debug神器.... 这个题暴力C(25,7)就可以过了，但是能剪枝尽量剪 比如(7 - cur + sum < 4) 还有判断是否在路径内的时候 如果有比待查元素大的 那肯定不在了 因为C 25,7 的生产过程是顺序的 代码如下:

#include 
       
        #include 
        
         #include 
         
          using namespace std;int map[6][6]={
     0};//存储地图int path[7]={
     0};//存储路径//上下左右的dx,dyint dx[4] = {
     0,0,-1,+1};int dy[4] = {+1,-1,0,0};bool vis[32]={
     false};//记录是否走过struct Point{    int x;    int y;    int id;    Point(){        x = y = id = 0 ;    }    Point(int a,int b){        x = a;        y = b;        id = y + (x-1)*5;    }    Point(int pid){        id = pid;        y = id % 5;        if(y==0 and id>0)            y = 5;        x = (id-1)/5 + 1 ;    }    //返回这个点是否在当前组成的path中    bool isInPath(){        for (int i = 0; i < 7; ++i)            if(path[i]==id)                return true;            else if(path[i] > id)                return false;        return false;    }};Point que[50];//初始化输入地图void init(){    for (int i = 1; i <= 5; ++i)    {        for (int j = 1; j <= 5; ++j)        {            char t;            cin>>t;            if(t=='J')                map[i][j]=1;        }    }}//对path进行合法性判断inline bool Check(){    memset(vis,0,sizeof(vis));    //bfs去检查路径    //queue
          
            q;    int front = 0;    int tail = 0;    Point start = path[0];    //q.push(start);//把起点放入    que[tail++] = start;    int sum = map[start.x][start.y];    int cur = 1;    while(front < tail){    //如果队列非空        Point& now = que[front];        front++;        vis[now.id] = true;//标志走过        //把周围的四个点里在当前组合里的点压入队列并且累积并且标志走过        for (int i = 0; i < 4; ++i)        {            Point next(now.x + dx[i],now.y + dy[i]);            if(next.x >5 or next.x < 1 or next.y > 5 or next.y < 1)                continue;//边界            if(!vis[next.id] and next.isInPath()){                vis[next.id] = true;                cur++;                sum += map[next.x][next.y];                //此处可以进行剪枝                if(7 - cur + sum < 4)                    return false;                que[tail++] = next;            }        }    }    return (cur==7 and sum>=4);}//计算int Build(){    int ans = 0;    //C(25,7)枚举组合    for(path[0]=1; path[0]<=19; path[0]++)    for(path[1]=path[0]+1; path[1]<=20; path[1]++)    for(path[2]=path[1]+1; path[2]<=21; path[2]++)    for(path[3]=path[2]+1; path[3]<=22; path[3]++)    for(path[4]=path[3]+1; path[4]<=23; path[4]++)    for(path[5]=path[4]+1; path[5]<=24; path[5]++)    for(path[6]=path[5]+1; path[6]<=25; path[6]++){        ans += Check();  //       if(Check()){        //     for (int i = 0; i < 7; ++i)        //     {        //         cout<
           
            <<" ";        //     }cout<
           
          
         
        
       

注意...STL的队列好慢好慢的...大概3600ms左右 自己写的是正好500..非常爽

另外Point构造函数里面坐标的处理要注意边界，还有就是在入队的同时设置为visited 否则会重复入队