| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2235 人关注过本帖
标题:ZOJ的2016题Segmentation Fault求解!
只看楼主 加入收藏
wmf2014
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:216
帖 子:2039
专家分:11273
注 册:2014-12-6
收藏
得分:0 
回复 7楼 beyondyf
欧拉路径是不是通过节点找最简路径(好像老鼠走迷宫)?这题和欧拉路径还是有区别吧,这题是不是只要输入的单词连成串就行了?

能编个毛线衣吗?
2015-05-11 09:46
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
回复 11楼 wmf2014
不是。两码事。你说那是迪杰斯特拉、弗洛伊德算法之类。解这题时我会用到一点,但用它只是判断图的连通性,而算法的核心是欧拉路径。

看来100分还不足以鼓舞士气,那再追加100分

重剑无锋,大巧不工
2015-05-11 10:13
wmf2014
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:216
帖 子:2039
专家分:11273
注 册:2014-12-6
收藏
得分:0 
回复 12楼 beyondyf
这题是不是一个单词尾部对应多个单词头部,最终你要找到一条链路和最后一个单词相连的链路?这样一来,算法就必须识别环路和断头路是吗?

能编个毛线衣吗?
2015-05-11 10:56
azzbcc
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:江西财经大学
等 级:贵宾
威 望:81
帖 子:3293
专家分:12919
注 册:2012-11-4
收藏
得分:0 
没账号没法验证,一个想法没有证明...
程序代码:
#include <stdio.h>
#include <string.h>

#define MAX    26
#define SIZE   27
#define LENGTH 1000

int ans[SIZE][SIZE] = { 0 };

int fun()
{
    int i, tmp, res;

    for (i = 0;i < SIZE;i++)
    {
        tmp = abs(ans[i][MAX] - ans[MAX][i]);
        if (tmp > 1)  return 1;
        res += tmp;
    }
    // 链路或环路
    return res != 0 && res != 2;
}

int main()
{
    int T, N;
    int begin, end, length;
    char str[LENGTH] = { 0 };

    for (scanf("%d", &T);T--;)
    {
        memset(ans, 0, sizeof(int) * SIZE * SIZE);
        for (scanf("%d", &N);N--;)
        {
            scanf("%s", str);
            length = strlen(str);
            begin  = str[0] - 'a';
            end    = str[length - 1] - 'a';
            ans[begin][end] += 1;
            ans[begin][MAX] += 1;
            ans[MAX][end]   += 1;
        }
        printf("%s\n", fun(ans) ? "The door cannot be opened." : "Ordering is possible.");
    }

    return 0;
}


[fly]存在即是合理[/fly]
2015-05-11 12:29
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
回复 14楼 azzbcc
思路是对的,但这段代码考虑的细节还不够。

没帐号?注册一个呗。

重剑无锋,大巧不工
2015-05-11 12:43
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
回复 13楼 wmf2014
只要确认能(或不能)把所有单词都串起来就行,不需实际串。n

重剑无锋,大巧不工
2015-05-11 12:46
resign
Rank: 1
等 级:新手上路
帖 子:18
专家分:2
注 册:2015-3-13
收藏
得分:0 
回复 9楼 beyondyf
这么一说,真的好像什么都不知道.
2015-05-11 13:19
wmf2014
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:216
帖 子:2039
专家分:11273
注 册:2014-12-6
收藏
得分:0 
回复 14楼 azzbcc
大哥,你这代码本机运行验证没有?前面函数fun没参数,后面printf时又有参数,考虑到你函数里使用的是全局变量,我帮你把printf里修改成没参数的,怎么弄都显示“The door cannot be opened”,结果不对啊。
通过beyondyf版主解释,只要把单词串起来就行,因此应该不能考虑单词输入的顺序,实际上“ab,ca,bb”应该是"Ordering is possible.",因为“ca-ab-bb”可以将单词连成串。我觉得用递归方法解决,容我空下来挑战下。

能编个毛线衣吗?
2015-05-12 05:54
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
差点忘了我有贴子置顶的权限。不过不打算在这里用了。这个问题挺有趣,值得置顶。只不过这里没有了曾几何时的算法交流氛围。往矣,置顶何益。

重剑无锋,大巧不工
2015-05-13 23:15
wmf2014
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:216
帖 子:2039
专家分:11273
注 册:2014-12-6
收藏
得分:0 
用递归解决,实验数据运行可行,请beyondyf版主测试下。
程序代码:
#include <stdio.h>
struct node
{
    int next;
    char *p;
};
int find(node *p,int dp,int l)
{
    int i,j;
    char a;
    for(i=0,j=0;i<l;i++)
    {
        if(p[i].next >=0)j++;
    }
    if(j==l-1)
        return 1;  //如果连成串则返回
    for(i=0;p[dp].p[i];i++); 
    a=p[dp].p[i-1];          //找到字符串尾部字符
    for(i=0;i<l;i++)
    {
        if(i!=dp&&p[i].next <0&&p[i].p[0]==a)
        {
            p[dp].next =i;
            if (find(p,i,l))
                return 1;
            else
                p[dp].next =-1;
        }
    }
    return 0;
}
void main()
{
    int i,j;
    char a[6][10]={"ab","ac","bd","ea","cq","da"};
    /*只需定义一个上限为1000的char型数组,然后根据输入再堆里申请实际长度的char数组,
    并把指针赋值为结构数组cp相应的指针里,这样可不需要浪费空间*/
   
    node cp[6];  //node数组数量可以是题意里t从堆里申请
    for(i=0;i<6;i++)
    {
        cp[i].next =-1;
        cp[i].p=&a[i][0];
        printf("%s  ",a[i]);
    }
    printf("\n");
    for(i=0;i<6;i++)
    {
        if(find(cp,i,6))
        {
            printf("Ordering is possible.\n");
            j=i;
            while(cp[j].next >=0)
            {
                printf("%s-",a[j]);
                j=cp[j].next ;   //显示串链
            }
            printf("\n");
            return;
        }
    }
    printf("The door cannot be opened.\n");
}


能编个毛线衣吗?
2015-05-14 07:55
快速回复:ZOJ的2016题Segmentation Fault求解!
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.055140 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved