使用 rand 函数 debug

碰到一个题目

题目描述

玛雅人有一种密码，如果字符串中出现连续的2012四个数字就能解开密码。给一个长度为N的字符串，（2=<N<=13）该字符串中只含有0,1,2三种数字，问这个字符串要移位几次才能解开密码，每次只能移动相邻的两个数字。例如02120经过一次移位，可以得到20120,01220,02210,02102，其中20120符合要求，因此输出为1.如果无论移位多少次都解不开密码，输出-1。

输入

第一行输入N，第二行输入N个数字，只包含0，1，2

输出

样例输入

5
02120

样例输出

1

虽然知道是bfs,但实现起来总觉得哪里不对,参考大佬们的博客后解决了几个难点:

• 存储类型 虽然题目说是输入n个数,但是使用字符串存储会使后续的处理更方便,题目出处九度OJ_1482输入写的也是长度为n的字符串

• hash_fun函数 对于每一个由 0 1 2 构成的,长度不超过13的字符串,可以将其当做一组3进制数,可以将其映射成10进制后共有3 ^ 13 = 1594323种可能

代码:

bool vis[1600000];
int hash_fun(string x)
{
    int ret = 0;
    for(int i = 0; i < n; i++)
        ret = ret*3 + x[i] -'0';
    return ret;
}

• 每一步的存储 虽然只有 字符串 这一个量,但是为了计步方便,仍定义node数据类型

代码:

struct node
{
    string pwd;
    int step;
};

解决的这几个小问题后,开始写

对应bfs模板,分分钟撸出代码

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;
 
int n;
string pwd;
bool vis[1600000];
 
struct node
{
    string pwd;
    int step;
};
 
bool check(string pwd)
{
    for(int i = 0; i < n-3; i++)
        if(pwd[i] == '2' && pwd[i+1] == '0' && pwd[i+2] == '1' && pwd[i+3] == '2')
            return 1;
    return 0;
}
 
int hash_fun(string x)
{
    int ret = 0;
    for(int i = 0; i < n; i++)
        ret = ret*3 + x[i] -'0';
    return ret;
}
 
int bfs()
{
    queue<node> q;
    node now, next;
    now.pwd = pwd;
    now.step = 0;
    q.push(now);
    vis[hash_fun(now.pwd)] = 1;
    while(!q.empty())
    {
        now = q.front();
        q.pop();
        if(now.step > 1600000)
            return -1;
        if(check(now.pwd))
            return now.step;
        for(int i = 1; i < n; i++)
        {
            swap(now.pwd[i], now.pwd[i-1]);
            next.pwd = now.pwd;
            next.step = now.step+1;
            if(!vis[hash_fun(next.pwd)])
            {
                q.push(next);
                vis[hash_fun(next.pwd)] = 1;
            }
            swap(now.pwd[i-1], now.pwd[i]);
        }
    }
}
 
int main()
{
    // freopen("input.txt", "r", stdin);
    while(scanf("%d", &n) == 1)
    {
        if(n < 4)
        {
            printf("-1\n");
            continue;
        }
        memset(vis, 0, sizeof(vis));
        cin >> pwd;
        int cnt[3] = {0};
        for(int i = 0; i < n; i++)
        {
            if(pwd[i] == '0')
                cnt[0]++;
            if(pwd[i] == '1')
                cnt[1]++;
            if(pwd[i] == '2')
                cnt[2]++;
        }
        if(cnt[0] < 1 || cnt[1] < 1 || cnt[2] < 2)
        {
            printf("-1\n");
            continue;
        }
        printf("%d\n", bfs());
    }
 
    return 0;
}

复制 提交

运行错误 50%

Runtime Error:Segmentation fault

嗯,段错误.

因为样例是没问题的,所以使用rand()函数生成随机数据进行测试

#include <cstdio>
#include <cstdlib>

int main()
{
    freopen("input.txt", "w", stdout);
    for(int i = 0; i < 100; i++)
    {
        int t = rand() % 14;
        if(t == 1 || t == 0)
            continue;
        printf("%d\n", t);
        for(int j = 0; j < t; j++)
            printf("%d", rand()%3);
        printf("\n");
    }
}

使用默认种子的rand()函数是为了重现有问题的数据

果然,跑了一遍就发现错误了

第一个if判断过早,如果n < 4将不会执行77行的cin >> pwd;

将77行提到70行后面,提交,AC

道理很简单,使用随机数据测试可以大大减少分析程序bug的时间,所以写点东西记一下

其实归根到底还是自己太菜了.