业界良心毒瘤

回复帖子

@Godstewchry 2019-06-12 13:31 回复

调了五个月的题了(六个月?),还有一个$\texttt {WA}......$

题目

$\mathcal Code:$

#define F_out(x) freopen(x".out","w",stdout)
#define F_in(s) freopen(s".in","r",stdin)
#define lal int
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
struct BFS_queue{
    char map[5][5];
    lal sum;
    lal step;
}serch[700000];
bool w[700000];
char a[4][4],b[4][4];
lal nex[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
lal begin,end;
lal t;
void input()
{
    lal i;
    for(i=0;i<4;i++)
    {
        cin>>a[i];
        for(lal j=0;j<4;j++)
            serch[0].map[i][j]=a[i][j];
    }
    for(i=0;i<4;i++)
        cin>>b[i];
}
lal state_red(lal num)
{
    t=0;
    lal i,j;
    lal need=0;
    for(i=3;i>=0;i--)
        for(j=3;j>=0;j--)
        {
            need+=(serch[num].map[i][j]-'0')<<t;
            t++;
        }
    return need;
//  cout<<begin<<endl;
//  cout<<end<<endl;
}
void bfs()
{
    lal i,j,k;
    lal head=0,tail=1;
    serch[head].sum=begin;
    w[begin]++;
    serch[head].step=0;
    while(head<tail)
    {
        if(serch[head].sum==end)
        {
            printf("%d\n",serch[head].step);
            return;
        }
        for(k=0;k<4;k++)
        {
            for(j=0;j<4;j++)
            {
                if(serch[head].map[k][j]-'0')
                {
                    for(i=0;i<4;i++)
                    {
                        lal tx,ty;
                        tx=k+nex[i][0];
                        ty=j+nex[i][1];
                        if(tx<0 || ty<0 ||tx>=4 || ty>=4 || serch[tail].map[tx][ty]=='1')
                            continue;
                        for(int g=0;g<4;g++)
                        { 
                            for(int h=0;h<4;h++)
                            { 
                                serch[tail].map[g][h]=serch[head].map[g][h];
                            }
                        } 
                        swap(serch[tail].map[k][j],serch[tail].map[tx][ty]);
                        serch[tail].sum=state_red(tail);
                        if(!w[serch[tail].sum])
                        { 
                            serch[tail].step=serch[head].step+1;
                            w[serch[tail].sum]=1;
                            tail++;
                        }
                    }
                }
            }
        }
        head++;
    }
}
int main()
{
    //F_in("");
    //F_out("");
    input();
    for(int i=3;i>=0;i--)
    {
        for(int j=3;j>=0;j--)
        {
            begin+=(a[i][j]-'0')<<t;
            end+=(b[i][j]-'0')<<t;
            t++;
        }
    }
    if(begin==end)
    {
        printf("0");
        return 0;
    }
    bfs();
    return 0;
}

最新评测结果

@smarthehe 2019-06-12 13:36 回复 举报

有那么长吗。。。

现在没时间,先发下代码您可以对照一下

@Godstewchry

#include <iostream>
#include <cstdio>
using namespace std;
struct zt
{
    bool sq[4][4];
    int step;
} q[(int)1e6];
bool book[1<<16];
int h,t=1,nxt[2][2]={{1,0},{0,1}};
int hash(zt a)
{
    int ret=0,i,j,s=1<<15;
    for(i=0;i<4;i++)
    {
        for(j=0;j<4;j++)
        {
            ret+=s*a.sq[i][j];
            s>>=1;
        }
    }
    return ret;
}
int main()
{
    zt tmp;
    int i,j,k,aim;
    for(i=0;i< 1<<16;i++) book[i]=0;
    for(i=0;i<4;i++)
    {
        for(j=0;j<4;j++) q[h].sq[i][j]=getchar()-'0';
        getchar(),getchar();
    }
    book[hash(q[h])]=1;
    getchar(),getchar();
    for(i=0;i<4;i++)
    {
        for(j=0;j<4;j++) tmp.sq[i][j]=getchar()-'0';
        getchar(),getchar();
    }
    aim=hash(tmp);
    if(hash(q[h])==aim)
    {
        printf("0");
        return 0;
    }
    while(h!=t)
    {
        tmp=q[h];
        for(i=0;i<4;i++)
        {
            for(j=0;j<4;j++)
            {
                for(k=0;k<2;k++)
                {
                    int tx=i+nxt[k][0],ty=j+nxt[k][1];
                    if(tx>=4||ty>=4) continue;
                    zt tt=tmp;
                    swap(tt.sq[i][j],tt.sq[tx][ty]);
                    int th=hash(tt);
                    if(th==aim)
                    {
                        printf("%d",tt.step+1);
                        return 0;
                    }
                    if(book[th]) continue;
                    book[th]=1;
                    tt.step=tmp.step+1;
                    q[t++]=tt;
                }
            }
        }
        h++;
    }
    return 0;
}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。