HDOJ1181变形课 深搜回溯

举报
谙忆 发表于 2021/05/27 00:49:27 2021/05/27
【摘要】 变形课 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碰到了一点小麻烦...

变形课
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"); }
}

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64

下面这段代码是从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"); }
}

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64

文章来源: chenhx.blog.csdn.net,作者:谙忆,版权归原作者所有,如需转载,请联系作者。

原文链接:chenhx.blog.csdn.net/article/details/47973353

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

举报
请填写举报理由
0/200