杭电-尊龙官方平台

杭电-pid1181-变形课

el/2024/3/25 17:04:44

杭电-pid1181-变形课

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.

hint

harry 可以念这个咒语:"big-got-them".

解题思路:

其实我们可以将每个字母想成一个一个的顶点,输入的的数据可以得出边,也就是顶点与顶点之间的关系。

注意这里是有向图(边有方向)。

实际就是告诉你很多边,然后求一个点能不能到达另外一个点。

可以使用dfs或者bfs。

dfs:

#include 
#include 
#include int mark[26];
int map[26][26];
int endpoint = 'm' - 'a';int dfs(int curpoint)
{if (curpoint == endpoint){return 1;}int i;for (i = 0; i < 26; i  ){if (map[curpoint][i] == 1 && mark[i] == 0){mark[i] = 1;int result = dfs(i);if (result == 1){return 1;}mark[i] = 0;}}return 0;
}int main()
{char s[1001];while (scanf("%s", s) != eof){memset(mark, 0, sizeof(mark));memset(map, 0, sizeof(map));while (s[0] != '0'){int len = strlen(s);map[s[0] - 97][s[len - 1] - 97] = 1;scanf("%s", s);}int result = dfs('b' - 'a');if (result){printf("yes.\n");}else{printf("no.\n");}}return 0;
}

bfs:

#include 
#include 
#include int main()
{int mark[26];int queue[26];int map[26][26];char s[1000];int endpoint = 'm' - 'a';while (scanf("%s", s) != eof){memset(mark, 0, sizeof(mark));memset(queue, 0, sizeof(queue));memset(map, 0, sizeof(map));while (s[0] != '0'){int x = s[0] - 'a';int y = s[strlen(s) - 1] - 'a';map[x][y] = 1;scanf("%s", s);}queue[0] = 'b' - 'a';int head = 0;;int tail = 1;int flag = 0;while (head < tail){int curpoint = queue[head];if (curpoint == endpoint){flag = 1;break;}int i;for (i = 0; i < 26; i  ){if (map[curpoint][i] == 1 && mark[i] == 0){queue[tail] = i;mark[i] = 1;tail  ;}}head  ;}if (flag == 1){printf("yes.\n");}else{printf("no.\n");}}return 0;
}

可以使用floyd算法。

floyd算法是求多源最短路径的算法。

我们的问题可以转化为:

使用floyd求出每两个点之间的最短距离,看看这个最短距离是不是可达的(即与我们初始化的infinity进行比较)。

floyd:

#include 
#include 
#include int main()
{int map[26][26];char s[1001];int infinity = 99999999;int endpoint = 'm' - 'a';while (scanf("%s", s) != eof){int i, j, k;for (i = 0; i < 26; i  ){for (j = 0; j < 26; j  ){map[i][j] = infinity;}}while (s[0] != '0'){int x = s[0] - 'a';int y = s[strlen(s) - 1] - 'a';map[x][y] = 1;scanf("%s", s);}for (k = 0; k < 26; k  ){for (i = 0; i < 26; i  ){for (j = 0; j < 26; j  ){if (map[i][k] < infinity && map[k][j] < infinity && map[i][j] > map[i][k]   map[k][j]){map[i][j] = map[i][k]   map[k][j];}}}}if (map['b' - 'a']['m' - 'a'] < infinity){printf("yes.\n");}else{printf("no.\n");}}return 0;
}

http://www.ngui.cc/el/5127162.html

相关文章

杭电-pid1008-elevator

杭电-pid1008-elevator 好吧,其实这道题是水过去的。。 problem description the highest building in our city has only one elevator. a request list is made up with n positive numbers. the numbers denote at which floors the elevator will stop, in s…

杭电-pid1012-u calculate e

杭电-pid1012-u calculate e #include #include int main() {printf("n e\n- -----------\n0 1\n1 2\n2 2.5\n");double num 2.5;double base 2;int i 3;while (i < 10){base base * i;num num 1 / base;printf("%d %…

杭电-pid1013-digital roots

杭电-pid1013-digital roots 九余数定理 #include using namespace std;int main() {string s;while (cin>>s){if (s[0] 0){break;}int sum 0, i;for (i 0; i < s.length(); i){sum sum s[i] - 0;}if (sum % 9 0){cout<<"9"<…

linux:curl的使用

linux:curl的使用 curl is a tool to transfer data from or to a server, using one of the supported protocols (http, https, ftp, ftps, tftp, dict, telnet, ldap or file). the command is designed to work without user interaction. curl支持多种协…

c/c :类型转换

c:dynamic_cast、static_cast 实验环境: [test1280localhost ~]$ uname -a linux localhost.localdomain 2.6.18-371.el5 #1 smp thu sep 5 21:21:44 edt 2013 x86_64 x86_64 x86_64 gnu/linux …… gcc 版本 4.1.2 20080704 (red hat 4.1.2-54) c/c中…

lua:ipairs/pairs

lua:ipairs/pairs lua中有两个很类似的函数:ipairs以及pairs。 实验环境: [test1280localhost 20170531]$ uname -a linux localhost.localdomain 2.6.18-371.el5 #1 smp thu sep 5 21:21:44 edt 2013 x86_64 x86_64 x86_64 gnu/linux [te…

常用linux命令:ssh

常用linux命令:ssh 以后随时记录一些工作中用到的命令,这些命令是常用的,但是参数可能比较多,容易混淆,不是很容易记住;也有可能某天忽然间需要用了,还要man一下就… 总之吧,这里讲…

常用linux命令:scp

常用linux命令:scp 传输文件,由本机传输至远端: scp -oport19222 /home/test1280/test.json test128010.1.70.206:/home/test1280 scp -oport19222 test.json test128010.1.70.206:/home/test1280scp -oportport localpath usernameip:desta…

常用linux命令:grep

常用linux命令:grep 1.搜索当前目录下关键字 [test1280localhost log]$ grep -nr "*" ./* ./ismpbus.log:18:2017/05/22 09:13:11.284 info - * open a subserver socket from 127.0.0.1,m_sockfd8,port12600. ./ismpbus.log:25:2017/05/22 09:13:11.28…

socket理解(1)

socket理解(1) 事情的起因是这样子的: 今天下午配置一个jdbc,使用的是informix数据库,按照往常的配置完毕后,无论如何也链接不到informix-server,导致java一直报错。 一开始我的jdbc是&#…
网站地图