uva321 bfs搜索

题意容易理解，思路 是将所在的房间号和r个房间的开灯情况作为一个状态，这样最多会有10*2^10种状态，并不多。然后就是bfs宽度遍历了，要注意一点是人在某个房间中不可以把该房间的灯关上，所以我在输入的灯开关数组时候就做了一个判断，如果两个数字相同，也即控制该房间灯的开关就在这个房间时，开关是无效的（很不符合常理~~）这样就保证了之后开关灯的合法性。

#include  
#include  
#include  
using namespace std;  
  
const int MAXSIZE = 60000;  
const int N=11;  
  
struct state  
{  
    int room[N];  
    int location,behave;  
};  
  
int r,d,s,front,rear,step,prestate[MAXSIZE];  
bool flag,door[N][N],swit[N][N],vis[N][1025];  
state target,S[MAXSIZE];  
void init()  
{  
    memset(swit,0,sizeof(swit));  
    memset(door,0,sizeof(door));  
    memset(S,0,sizeof(S));  
    memset(vis,0,sizeof(vis));  
    S[0].room[1]=1;  
    S[0].location=1;  
    vis[1][1]=1;  
    target.location=r;  
    memset(target.room,0,sizeof(target.room));  
    target.room[r]=1;  
}  
int caldex(state s)  
{  
    int dex=0,exp=1;  
    for (int i=1;i<=r;i++)  
    {  
        dex=dex+s.room[i]*exp;  
        exp=exp << 1 ;  
    }  
    return dex;  
}  
bool compare(state s)  
{  
    if (s.location==target.location)  
    {  
        for (int i=1;i<=r;i++)  
        {  
            if (s.room[i]!=target.room[i])  
                return 0;  
        }  
        return 1;  
    }  
    return 0;  
}  
void bfs()  
{  
    front=0;rear=1,step=0,flag=0;  
    while (front





300)  
    {  
        cout<<"Move to room "<>r>>d>>s&&r)  
    {  
        col++;  
        init();  
        for (int i=0;i>m>>n;  
            door[m][n]=door[n][m]=1;  
        }  
        for (int i=0;i>m>>n;  
            if (m!=n)  
                swit[m][n]=1;  
        }  
        bfs();  
        cout<<"Villa #"<=0;j--)  
            {  
                print(S[result[j]]);  
            }  
            delete result;  
        }  
        else cout<<"The problem cannot be solved."<