搜索专题: HDU1501Zipper
Zipper
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 10465 Accepted Submission(s): 3762
For example, consider forming "tcraete" from "cat" and "tree":
String A: cat
String B: tree
String C: tcraete
As you can see, we can form the third string by alternating characters from the two strings. As a second example, consider forming "catrtee" from "cat" and "tree":
String A: cat
String B: tree
String C: catrtee
Finally, notice that it is impossible to form "cttaree" from "cat" and "tree".
set per line.
For each data set, the line of input consists of three strings, separated by a single space. All strings are composed of upper and lower case letters only. The length of the third string is always the sum of the lengths of the first two strings. The first two
strings will have lengths between 1 and 200 characters, inclusive.
Data set n: yes
if the third string can be formed from the first two, or
Data set n: no
if it cannot. Of course n should be replaced by the data set number. See the sample output below for an example.
3
cat tree tcraete
cat tree catrtee
cat tree cttaree
Data set 1: yes
Data set 2: yes
Data set 3: no
RunId : 21249294 Language : G++ Author : hnustwanghe
Code Render Status : Rendered By HDOJ G++ Code Render Version 0.01 Beta
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int N = 200 + 5;
char a[N],b[N],c[2*N];
bool visit[N][N],can_find;
void DFS(int i,int j,int k){
if(can_find || visit[i][j]) return;
if(c[k]=='\0'){can_find = true;return;}
visit[i][j] = true;
if(a[i]!='\0' && a[i] == c[k])
DFS(i+1,j,k+1);
if(b[j]!='\0' && b[j] == c[k])
DFS(i,j+1,k+1);
}
int main(){
int T,cnt=0;
scanf("%d",&T);
while(T--){
scanf("%s %s %s",a,b,c);
memset(visit,0,sizeof(visit));
can_find = false;
DFS(0,0,0);
printf("Data set %d: %s\n",++cnt,can_find?"yes":"no");
}
return 0;
}
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int N = 200 + 5;
char a[N],b[N],c[2*N];
bool visit[N][N],can_find; void DFS(int i,int j,int k){
if(can_find || visit[i][j]) return;
if(c[k]=='\0'){can_find = true;return;}
visit[i][j] = true;
if(a[i]!='\0' && a[i] == c[k])
DFS(i+1,j,k+1);
if(b[j]!='\0' && b[j] == c[k])
DFS(i,j+1,k+1);
}
int main(){
int T,cnt=0;
scanf("%d",&T);
while(T--){
scanf("%s %s %s",a,b,c);
memset(visit,0,sizeof(visit));
can_find = false;
DFS(0,0,0);
printf("Data set %d: %s\n",++cnt,can_find?"yes":"no");
}
return 0;
}
最新文章
- C#设计模式-策略者模式
- 分布式入门之1:Lease机制
- servlet学习笔记_4
- DNS bind子域授权安装
- 《你必须知道的.NET》读书笔记三:体验OO之美
- python之基本数据类型
- Ajax异步刷新局部页面的小李子
- Nginx 之并发优化
- JSP图片上传 公共工具类
- 关于解决Oracle登录:ora-12154:tns:无法解析指定的连接标识符
- .net抓取网页数据
- android:layout_weight属性的简单使用
- 微软HoloLens虚拟现实可以开发了。
- Mysql数据库连接查询
- 通过DNS传输后门来绕过杀软
- 笔记:Maven 插件及配置详解
- delphi 组件安装教程详解
- 唯一约束(UNIQUE_KEY)
- MVVM 简介
- MySQL Replication--修改主键为NULL导致的异常
热门文章
- 12. ClustrixDB 为容错和可用性分配磁盘空间
- PHP开发环境 PHP培训教程
- 157. [USACO Nov07] 奶牛跨栏(第三次考试大整理)
- c#翻页效果
- VS Code报错Module &#39;xx&#39; has no &#39;xx&#39; member pylint(no-member)解决办法
- Linux安装部署FTP服务器
- 测试String——StringBuffer——StringBulider的速度
- Linux shell - cut命令用法(转载)
- JavaScript apply
- C++引用与传参