HDOJ1181变形课 深搜回溯

简介: 变形课 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others) Total Submission(s): 18474 Accepted Submissio...

变形课
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others)
Total Submission(s): 18474 Accepted Submission(s): 6663

Problem Description
呃……变形课上Harry碰到了一点小麻烦,因为他并不像Hermione那样能够记住所有的咒语而随意的将一个棒球变成刺猬什么的,但是他发现了变形咒语的一个统一规律:如果咒语是以a开头b结尾的一个单词,那么它的作用就恰好是使A物体变成B物体.
Harry已经将他所会的所有咒语都列成了一个表,他想让你帮忙计算一下他是否能完成老师的作业,将一个B(ball)变成一个M(Mouse),你知道,如果他自己不能完成的话,他就只好向Hermione请教,并且被迫听一大堆好好学习的道理.

Input
测试数据有多组。每组有多行,每行一个单词,仅包括小写字母,是Harry所会的所有咒语.数字0表示一组输入结束.

Output
如果Harry可以完成他的作业,就输出”Yes.”,否则就输出”No.”(不要忽略了句号)

Sample Input
so
soon
river
goes
them
got
moon
begin
big
0

Sample Output
Yes.

HintHint
Harry 可以念这个咒语:”big-got-them”.

这个代码还是很容易理解的,经典的DFS
不过对于没超时,我感到意外哈
我是从m往b搜索的

#include<stdlib.h>
#include<stdio.h>
#include <string.h>
using namespace std;
char a[1000][50];
int len[1000];
int k;int flag;
bool vis[1000];
void dfs(char x)
{
    if(x=='b')
        {
            flag=1;
            return ;
        }
    if(flag==1)
    {
        return;
    }
    for(int i=0;i<k;i++)
    {
        //printf("vis[%d]=%d\n",i,vis[i]);
        if(vis[i]==0)
        {
            if(a[i][len[i]]==x)
            {
   // printf("a[%d][%d]=%c\n",i,len[i],a[i][len[i]]);
                vis[i]=1;
               // printf("x=%c\n",x);
                dfs(a[i][0]);
               // printf("x=%c\n",x);
                vis[i]=0;
            }
        }
    }
}
int main()
{
    while(scanf("%s",a[0])!=EOF)
    {
        flag=0;
         int i=0;
        if(a[0][0]=='0')
        {
            printf("no.\n");
            continue;
        }
        memset(vis,0,sizeof(vis));
        while(a[i][0]!='0')
        {
            len[i]=strlen(a[i])-1;
            i++;
            scanf("%s",a[i]);
        }
        k=i;
        dfs('m');
        if(flag==1)
            printf("Yes.\n");
        else
            printf("No.\n");

    }
}

下面这段代码是从b往m搜索的,差不多

#include<stdlib.h>
#include<stdio.h>
#include <string.h>
using namespace std;
char a[1000][50];
int len[1000];
int k;int flag;
bool vis[1000];
void dfs(char x)
{
    if(x=='m')
        {
            flag=1;
            return ;
        }
    if(flag==1)
    {
        return;
    }
    for(int i=0;i<k;i++)
    {
        //printf("vis[%d]=%d\n",i,vis[i]);
        if(vis[i]==0)
        {
            if(a[i][0]==x)
            {
               // printf("a[%d][%d]=%c\n",i,len[i],a[i][len[i]]);
                vis[i]=1;
               // printf("x=%c\n",x);
                dfs(a[i][len[i]]);
               // printf("x=%c\n",x);
                vis[i]=0;
            }
        }
    }
}
int main()
{
    while(scanf("%s",a[0])!=EOF)
    {
        flag=0;
         int i=0;
        if(a[0][0]=='0')
        {
            printf("no.\n");
            continue;
        }
        memset(vis,0,sizeof(vis));
        while(a[i][0]!='0')
        {
            len[i]=strlen(a[i])-1;
            i++;
            scanf("%s",a[i]);
        }
        k=i;
        dfs('b');
        if(flag==1)
            printf("Yes.\n");
        else
            printf("No.\n");

    }
}
目录
相关文章
|
8月前
|
C语言
快速幂+高精乘(填坑)洛谷1226+1045
快速幂+高精乘(填坑)洛谷1226+1045
|
算法 测试技术 C++
C++算法:美丽塔O(n)解法单调栈
C++算法:美丽塔O(n)解法单调栈
|
7月前
|
存储
【洛谷 P2437】蜜蜂路线 题解(递归+记忆化搜索+高精度)
蜜蜂路线问题:蜜蜂从蜂房$m$到$n$($m&lt;n$)按数字递增爬行。给定$m$和$n$,求路线数。示例:$m=1$,$n=14$,输出$377$。100%数据$1\leq m,n\leq1000$。使用斐波那契序列优化,高精度处理大数。代码实现斐波那契存储并动态规划求解。
114 0
|
7月前
|
机器学习/深度学习 人工智能
PTA之N个数求和(细节题)天梯赛
编程题,要求计算以分子/分母形式给出的一组有理数的和,输出结果也要是最简有理数形式。输入包含正整数N(N≤100)及N个有理数,输出为和的最简形式。示例:输入5个数2/5, 4/15, 1/30, -2/60, 8/3,输出3 1/3;输入2个数4/3, 2/3,输出2。代码中包含求最大公约数的函数和计算有理数和的主要逻辑。
65 0
|
8月前
|
人工智能
倍增LCA受到启发的一题
倍增LCA受到启发的一题
37 0
|
算法 JavaScript 前端开发
日拱算法:解两道“杨辉三角”题
什么是“杨辉三角”,想必大家并不陌生~~ 在「杨辉三角」中,每个数是它左上方和右上方的数的和。
leetcode每日一题:376. 摆动序列
leetcode每日一题:376. 摆动序列
LeetCode每日一题——790. 多米诺和托米诺平铺
有两种形状的瓷砖:一种是 2 x 1 的多米诺形,另一种是形如 “L” 的托米诺形。两种形状都可以旋转。
145 0
LeetCode每日一题——790. 多米诺和托米诺平铺
LeetCode每日一题——1823.找出游戏的获胜者(约瑟夫环问题)
共有 n 名小伙伴一起做游戏。小伙伴们围成一圈,按 顺时针顺序 从 1 到 n 编号。确切地说,从第 i 名小伙伴顺时针移动一位会到达第 (i+1) 名小伙伴的位置,其中 1 <= i < n ,从第 n 名小伙伴顺时针移动一位会回到第 1 名小伙伴的位置。
170 0
LeetCode每日一题——1823.找出游戏的获胜者(约瑟夫环问题)
|
算法 搜索推荐 Windows
从荷兰国旗问题出发,详解快速排序算法的原理
从荷兰国旗问题出发,详解快速排序算法的原理
177 0