洛谷P2622关灯问题

1678292-20190519192340454-474344052.png

具体解法是:对队首的某一状态,枚举每一个开关灯操作,记录到达这一新状态的步数(也就是老状态 + 1),若是最终答案,输出,若不是,压入队列。采用结构体记录每个节点,包含当前状态和步数。

#includebits/stdc++.h
using namespace std;
typedef struct{
    int status,cnt;
}NODE;
int vis[100020]={0};
int arr[200][200]={0};
int n,m;int num=0,min_step=9999;
queueNODE steps;

void bfs(int level)
{ 
    if(steps.empty())return;
    NODE pre_node=steps.front();
    steps.pop();
    if(pre_node.status==0)
    {
        coutpre_node.cnt;
        min_step=min(min_step,pre_node.cnt);
        return;
    }
    for(int i=1;i=m;i++)
    {//枚举所有状态
        NODE new_node=pre_node;
        int new_status=new_node.status;
        for(int j=1;j=n;j++)
        {
            if(arr[i][j]==1)
            {
                if(new_status(1(n-j)))//说明是1
                    new_status=new_status^(1(n-j));
            }
            if(arr[i][j]==-1)
            {
                new_status=new_status|(1(n-j));
            }
        }

        if(!vis[new_status])
        {
            new_node.status=new_status;
            new_node.cnt=level;
            steps.push(new_node);
            vis[new_status]=1;
        }
    }
    bfs(steps.front().cnt+1);
}
int main()
{
    cinnm;
    for(int i=0;in;i++)
        {
            num=(num1)+1;
        }
    NODE node={num,0};
    steps.push(node);
    for(int i=1;i=m;i++)
    {
        for(int j=1;j=n;j++)
            cinarr[i][j];
    }
    vis[num]=1;
    bfs(1);
    if(min_step==9999) cout-1endl;
    return 0;
}

较为简便的递推dp代码:

#includebits/stdc++.h
using namespace std;
vectorintdp(1025,-1);int arr[200][200];
int n,m;
int main()
{
    queueintq;
    cinnm;
    for(int i=1;i=m;i++)
    {
        for(int j=1;j=n;j++)
            cinarr[i][j];
    }
    q.push((1n)-1);dp[(1n)-1]=0;
    while(!q.empty())
    {
        
        int c_state=q.front();
        q.pop();
        for(int i=1;i=m;i++)
        {
            int n_state=c_state;
            for(int j=1;j=n;j++)
            {
                if(arr[i][j]==1)
                    if(n_state(1(n-j)))
                    n_state=n_state^(1(n-j));
                if(arr[i][j]==-1)
                    n_state=n_state|(1(n-j));
            }
            //coutdp[n_state]endl;
            if(dp[n_state]==-1)
            {   
                dp[n_state]=dp[c_state]+1;
                q.push(n_state);
            }
        }
    }
    coutdp[0]endl;
    return 0;
}

转载于:https://www.cnblogs.com/tldr/p/10890378.html

最新回复(0)
/jishueGx5zSEV34HnyAyZ07R5qhj0XWfKOOvr57j00Q_3D_3D4795013
8 简首页