排查了好久都是 WA,帮忙看下代码吧
  • 板块UVA1724 Solitaire
  • 楼主Pectics
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/11/15 23:14
  • 上次更新2023/11/16 11:27:39
查看原帖
排查了好久都是 WA,帮忙看下代码吧
483771
Pectics楼主2023/11/15 23:14

#include <iostream>

#include <queue>

#include <cstdint>

#include <string.h>

using namespace std;

struct caze

{

    bool state[8][8];

    int step;

};

bool viewed[635376] = {0};

const int dir[4][2] =

    {{-1, 0},

     {0, -1},

     {1, 0},

     {0, 1}};

bool start[8][8] = {{0}};

bool goal[8][8] = {{0}};

int c_num(int n, int m)

{

    if (n <= 0)

        return 0;

    uint64_t a = 1;

    uint64_t b = 1;

    while (m)

    {

        a *= n--;

        b *= m--;

    }

    return a / b;

}

int c_id(uint64_t seq)

{

    int m = 0;

    // 计算组合个数

    uint64_t seq_counter = seq;

    while (seq_counter != 0)

    {

        seq_counter &= (seq_counter - 1);

        ++m;

    }

    //cout<<"元素个数:"<<m<<endl;

    uint64_t seqid = 0;

    for (int i = 0; i < m; ++i)

    {

        int n = 0; // 该位的距离

        uint64_t st = (1 << i);

        //cout<<"seq: "<<toBin(seq)<<endl;

        uint64_t cp = (seq & ~(seq - 1));

        //cout<<"st: "<<toBin(st)<<endl;

        //cout<<"cp: "<<toBin(cp)<<endl;

        while (cp >> n != st)

            ++n;

        seq &= (seq - 1);

        // 代入函数进行计算

        uint64_t g = c_num(n + i, i + 1);

        //cout<<"adding("<<n<<","<<i<<"): "<<g<<endl;

        seqid += g;

    }

    return seqid;

}

uint64_t s_id(bool board[8][8])

{

    uint64_t result = 0;

    for (int i = 0; i < 8; ++i)

    {

        for (int j = 0; j < 8; ++j)

        {

            result <<= 1;

            if (board[i][j] == 1)

            {

                result |= 1;

            }

        }

    }

    return c_id(result);

}

int bfs()

{

    caze head;

    memcpy(head.state, start, sizeof(head.state));

    head.step = 0;

    queue<caze> q;

    viewed[s_id(head.state)] = 1;

    q.push(head);

    while (!q.empty())

    {

        head = q.front();

        if (head.step > 8)

        {

            q.pop();

            continue;

        }

        if (memcmp(head.state, goal, sizeof(goal)) == 0)

            return head.step;

        q.pop();

        for (int i = 0; i < 64; ++i)

        {

            int x = i / 8;

            int y = i % 8;

            if (head.state[x][y] == 1)

            {

                for (int j = 0; j < 4; ++j)

                {

                    int xn = x + dir[j][0];

                    int yn = y + dir[j][1];

                    if (head.state[xn][yn] == 1)

                    {

                        xn += dir[j][0];

                        yn += dir[j][1];

                    }

                    if (xn >= 0 && xn < 8 && yn >= 0 && yn < 8 && head.state[xn][yn] != 1)

                    {

                        caze cn;

                        memcpy(&cn, &head, sizeof(struct caze));

                        swap(cn.state[x][y], cn.state[xn][yn]);

                        ++cn.step;

                        int id = s_id(cn.state);

                        if (!viewed[id])

                        {

                            viewed[id] = 1;

                            q.push(cn);

                        }

                    }

                }

            }

        }

    }

    return -1;

}

int main()

{

    int x[4],y[4];

    while (~scanf("%d %d",&x[0],&y[0]))

    {

        for (int i=1;i<4;++i) {

            scanf("%d %d",&x[i],&y[i]);

        }

        for (int i=0;i<4;++i) {

            goal[x[i]][y[i]]=1;

        }

        for (int i=0;i<4;++i) {

            int a,b;

            scanf("%d %d",&a,&b);

            start[a][b]=1;

        }

        int s = bfs();

        if (s > 8 || s < 0)

            cout << "NO" << endl;

        else

            cout << "YES" << endl;

        memset(viewed,0,sizeof(viewed));

        memset(start,0,sizeof(start));

        memset(goal,0,sizeof(goal));

    }

    return 0;

}

2023/11/15 23:14
加载中...