128 条题解
-
2PowderHan LV 10 @ 2017-05-08 08:58:44
/* 很裸的一道搜索题啊 我们看这个数据范围就知道不写搜索都对不起出题人了 我们可以直接bfs+判重 判重我们知道,我们可以用hash,set,map等方法来做咯 这里为了好写一点 就用的set映射来判重 (闲的无聊实验证明了一下set会比map慢一点啊Orz) Orz还是速度还是可以的(不过NOIP最好还是手写hash叭) 然后这样直接bfs就很简单了 基本功吧 整个题目唯一的稍微的难点就在于字符串的处理了 感觉像是在考字符串? 我们怎么找到一个字符串中有没有可以变换的子串然后改变它 OTZ这很麻烦的鬼东西如果用数组的话 但是如果我们用string就很好做了 加上几个string的函数 就跟水题一样如履平地233333 然后随便乱搞叭 嗯就这样了 那段bfs扩展的字串处理有点复杂 也可以用自己的方法搞咯 */ #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <queue> #include <set> using namespace std; struct node { string s; int step; }; queue<node> q; set<string> vis; string start,to; string a[15]; string b[15]; int l=1; void init() { cin>>start>>to; while(cin>>a[l]>>b[l]) l++; node t; t.step=0; t.s=start; q.push(t); } void bfs() { node t; while(!q.empty()) { t=q.front(); q.pop(); if(t.step>10) break; if(t.s==to) { cout<<t.step<<endl; return; } if(!vis.count(t.s)) { vis.insert(t.s); for(int i=1;i<=l;i++) if(t.s.find(a[i])>=0) for(int j=t.s.find(a[i]);j>=0&&j<=(t.s.length()-a[i].length());j=t.s.find(a[i],j+1)) { node w=t; w.step++; w.s.replace(j, a[i].size(), b[i]); q.push(w); } } } cout<<"NO ANSWER!"<<endl; } int main() { init(); bfs(); return 0; }
-
12017-08-14 16:00:28@
低逼格题解。。。
实际上就是字符串BFS#include <iostream> #include <algorithm> #include <queue> #include <map> #include <string> #include <cstdio> #include <cstring> using namespace std; struct edgedata { string u,v; }; struct quedata { string str; int tmp; }; queue<quedata> que; map<string,bool> flag; edgedata edge[10]; string strs,stre; char Cstr1[25],Cstr2[25]; int edgesize; inline bool cmp(string &a,string &b) { if (a.size()!=b.size()) return 0; for (int i=0;i<(int)a.size();i++) if (a[i]!=b[i]) return 0; return 1; } inline int Read() { scanf("%s%s",Cstr1,Cstr2); strs=Cstr1,stre=Cstr2; for (edgesize=1;scanf("%s%s",Cstr1,Cstr2)!=EOF;edge[edgesize].u=Cstr1,edge[edgesize++].v=Cstr2); return --edgesize; } inline int Write(int arg) { if (arg==-1) printf("NO ANSWER!\n"); else printf("%d\n",arg); return 0; } int Push(quedata u,int tmp) { int pushsize=0; for (int list=u.str.find(edge[tmp].u);list!=(int)string::npos;list=u.str.find(edge[tmp].u,list+1),pushsize++) { quedata v=u; v.tmp++; v.str.erase(list,edge[tmp].u.size()); v.str.insert(list,edge[tmp].v); if (!flag[v.str]) que.push(v); flag[v.str]=1; } return pushsize; } int Bfs() { for (;!que.empty();que.pop()); quedata U; U.str=strs,U.tmp=0; que.push(U); for (;!que.empty();) { quedata u=que.front(); que.pop(); if (u.tmp>10) return -1; if (!strcmp(u.str.c_str(),stre.c_str())) return u.tmp; for (int i=1;i<=edgesize;i++) Push(u,i); } return -1; } int main() { Read(); int ret=Bfs(); Write(ret); return 0; }
-
02018-03-28 11:51:41@
//bfs 和自己写的字符串处理。
```cpp
#include <iostream>
#include<cstring>
#include<algorithm>
#include <queue>
#include <cstring>
#include <vector>
#include <map>
#include <set>
using namespace std;#define FileIn() freopen("input.txt","r",stdin);
#define SUPER_BREAK() exit(0);
#define test() cout << "OK \n" << flush;
#define WC(x) cout << (x) << " " << flush << endl;const int MAXLEN = 75;
const int MAX = 7;
char start[MAXLEN],tar[MAXLEN];
char a[MAX][MAXLEN],b[MAX][MAXLEN];
int cnt = 0;
set<string> vis;struct Node {
string str;
int step = 0;
};vector<int> hasIt(const string &pattern,char *s2) {
vector<int> v;
int len1 = pattern.length(),len2 = strlen(s2);
for(int i = 0,j = 0; i < len1; ++i) {
if(i + len2 > len1) break;
bool matched = true;
for(j = 0; j < len2; ++j) {
if(s2[j] != pattern[i+j]) {
matched = false;
break;
}
}
if(matched) v.push_back(i);
}
return v;// 返回匹配的下标序列
}int bfs() {
queue<Node> q;
Node s;
s.str = string(start);
q.push(s);
vis.insert(s.str);while(!q.empty()) {
Node u = q.front();
q.pop();
if(u.step > 10) return 0;
if(u.str == tar)
return u.step;vector<int> v;
for(int i = 0; i < cnt; ++i) {
Node nd;
char buf[MAXLEN];
nd.str = u.str;v = hasIt(u.str,a[i]);
if(v.size()) {
for(int k = 0; k < v.size(); ++k) { //串处理写的比较差
int p = v[k];
strcpy(buf,u.str.c_str());
strcpy(buf+p,b[i]);
if(strlen(buf) > 20) continue;
strcpy(buf+p+strlen(b[i]),u.str.c_str()+p+strlen(a[i]));
if(strlen(buf) > 20) continue;
nd.str = string(buf);if(!vis.count(nd.str)) {
nd.step = u.step + 1;
q.push(nd);
vis.insert(nd.str);
}
}
}}
}
return 0;
}int main(int argc, char const *argv[])
{
// FileIn();
cin >> start >> tar;
while(scanf(" %s %s",a[cnt],b[cnt]) != EOF) cnt ++;int ans = bfs();
if(ans == 0) cout << "NO ANSWER!";
else cout << ans;
return 0;
}
``` -
02016-09-24 08:35:45@
Map判重,单向BFS,一开始数组开小了,Wrong Answer3个点
```
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <map>using namespace std;
string A, B;
string from[10];
string to[10];
int n = 1;struct node
{
string s;
int step;
};queue<node> q;
map<string, int> visit;void work()
{
int i, j;
while (!q.empty())
{
struct node t;
t = q.front();
q.pop();
if (t.s == B && t.step <= 10)
{
cout<<t.step<<endl;
return;
}
if (t.step > 10)
return;
if (visit[t.s] == 0)
{
visit[t.s] = 1;
for (i = 1; i <= n; i++)
{
if (t.s.find(from[i]) >= 0)
{
for (j = t.s.find(from[i]); j >= 0 && j <= t.s.size() - from[i].size(); j = t.s.find(from[i], j + 1))
{
struct node w;
w = t;
w.step++;
w.s.replace(j, from[i].size(), to[i]);
q.push(w);
}
}
}
}
}
cout<<"NO ANSWER!"<<endl;
}int main()
{
node e;
cin>>A>>B;
while (cin>>from[n]>>to[n])n++;
n--;
e.s = A;
e.step = 0;
q.push(e);
work();return 0;
}
``` -
02016-09-03 21:59:22@
数据很小不需要剪枝,直接bfs即可
此题用STL做就如同做简单模拟题一样轻松
```c++
#include<iostream>
#include<cstdio>
#include<map>
#include<queue>
#include<string>
#include<vector>
using namespace std;struct Transform {
string from, to;
Transform (const string &from, const string &to) : from(from), to(to) {}
};string A, B;
map<string, int> d;
vector<Transform> transforms;bool bfs () {
queue<string> Q;
Q.push(A);
d[A] = 0;
while (!Q.empty()) {
string u = Q.front(); Q.pop();
if (d[u] > 10) return false;
if (u == B) return true;
for (int i = 0; i < transforms.size(); i++) {
const Transform &tool = transforms[i];
string C;
int p = u.find(tool.from);
while (p != string::npos) {
C = u;
C.replace(p, tool.from.size(), tool.to, 0, tool.to.size());
if (!d.count(C)) {
d[C] = d[u] + 1;
Q.push(C);
}
p = u.find(tool.from, p+1);
}
}
}
return false;
}int main ()
{
// freopen("in.txt", "r", stdin);
cin >> A >> B;
string from, to;
while (cin >> from >> to) transforms.push_back(Transform(from, to));if (bfs()) cout << d[B] << "\n";
else cout << "NO ANSWER!\n";
return 0;
}
``` -
02016-08-08 10:38:41@
mdzz为什么加上algorithm就编译不过??窝的Rp啊!!
- 测试数据 #0: Accepted, time = 0 ms, mem = 572 KiB, score = 10
- 测试数据 #1: Accepted, time = 0 ms, mem = 576 KiB, score = 10
- 测试数据 #2: Accepted, time = 0 ms, mem = 572 KiB, score = 10
- 测试数据 #3: Accepted, time = 0 ms, mem = 624 KiB, score = 10
- 测试数据 #4: Accepted, time = 93 ms, mem = 1080 KiB, score = 10Accepted, time = 93 ms, mem = 1080 KiB, score = 50
思路:迭代加深搜索+可行性剪枝。如果剩余步数为x时匹配str失败了,记mp[str] = x,那么当下一次匹配str且剩余步数少于mp[str],就注定失败。
```c++
#include <iostream>
#include <cstring>
#include <map>
#include <queue>
using namespace std;
string from, to;
map<string, int> mp;
string x[20], y[20];
int n = 1;
int lim = 1;
bool dfs(const string& str, const int now_depth)
{
//cout << str << endl;
if (now_depth > lim)
return 0;
if (str == to) return 1;
if (lim - now_depth <= mp[str])
return 0;
//cout << str << endl;
for (int k = 1; k < n; k++) {
string::size_type pp, last = -1;
string tmp = str;
while (1) {
pp = str.find(x[k], last+1);
if (pp != string::npos) {
tmp.replace(pp, x[k].size(), y[k]);
//cout << tmp << endl;
if (dfs(tmp, now_depth+1))
return 1;
//else mp[tmp] = max(mp[tmp], lim - now_depth-1);tmp = str;
last = pp;
} else break;
}
}
mp[str] = max(mp[str], lim-now_depth);
return 0;
}int main()
{
cin >> from >> to;
while (cin >> x[n] >> y[n]) n++;
for (; lim <= 10; lim++) {
if(dfs(from, 0)) {
cout << lim << endl;
return 0;
}
}
cout << "NO ANSWER!" << endl;
return 0;
} -
02016-07-13 20:01:17@
坑,这题一个键可以对应多个值,像这样
a->b
a->c
好多次才ac
附代码:
#include<iostream>
#include<string>
#include<cstdio>
#include<map>
#include<queue>
#include<set>
using namespace std;map<string,set<string> > g;
map<string,int> d;
string a,b;
queue<string> q;int bfs()
{
q.push(a);
for (d[a]=0;!q.empty();) {
string s=q.front(); q.pop();
if (s==b) return d[s];
if (d[s]>10) return -1;
for (map<string,set<string> >::iterator i=g.begin();i!=g.end();++i) {
string sub=i->first;
for (int j=0;j<s.size();++j) {
if (s.substr(j,sub.size())==sub) {
for (set<string>::iterator it=i->second.begin();it!=i->second.end();++it) {
string v(s.substr(0,j)+*it+s.substr(j+sub.size(),s.size()-j-sub.size()));
//cout<<v<<endl;
if (d.find(v)==d.end()) {
d[v]=d[s]+1;
//cout<<d[v]<<"new state:"<<v<<endl;
q.push(v);
}
}
}
}
}
}
return -1;}
int main()
{
//freopen("in.txt","r",stdin);
//int j=0;
//string s1("123456"),s2("www"),s3("12");
//cout<<s1.substr(0,j)+s2+s1.substr(j+s3.size(),s1.size()-j-s3.size());
cin>>a>>b;
string t,s;
while (cin>>t) {
//if (t.first==".") break;
string s; cin>>s;
g[t].insert(s);
}
int ans=bfs();
if (ans==-1) cout<<"NO ANSWER!";
else cout<<ans;
return 0;
} -
02016-03-23 07:26:42@
include <iostream> include <cstring> include <map> include <queue> include <algorithm>
using namespace std;
string f[21], t[21], a, b;
map<string, int> ff;
queue<string> q;
int tt = 1;
void bfs(string x)
{
while(!q.empty()) {
string x = q.front();
if(x == b)
return ;
if(ff[x] >= 11) {
q.pop();
continue;
}
for(int i = 1; i < tt; i++) {
int p = x.find(f[i]);
while(p < x.size()) {
string k = "";
k += x.substr(0, p), k += t[i];
k += x.substr(p + f[i].size(), x.size() - p - f[i].size());
if(ff[k] == 0 || ff[x] + 1 < ff[k])
ff[k] = ff[x] + 1, q.push(k);
p = x.find(f[i], p + 1);
}
}
q.pop();
}
}
int main() {
string x, y;
cin >> a >> b;
while(cin >> x >> y)
if(x != y)
f[tt] = x, t[tt++] = y;
q.push(a), ff[a] = 1;
bfs(a);
if(ff[b] == 0)
cout << "NO ANSWER!" << endl;
else
cout << ff[b] - 1 << endl;
return 0;
}
某些小人觉得我不会这么慷慨大方,所以,小人去shi!!! -
02016-03-23 07:24:54@
记录信息
评测状态 Accepted
题目 P1124 字串变换
递交时间 2016-03-21 07:45:29
代码语言 C++
评测机 ShadowShore
消耗时间 279 ms
消耗内存 1532 KiB
评测时间 2016-03-21 07:45:30评测结果
编译成功foo.cpp: In function 'void bfs(std::string)':
foo.cpp:24:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(p < x.size()) {
^测试数据 #0: Accepted, time = 15 ms, mem = 576 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 576 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 580 KiB, score = 10
测试数据 #3: Accepted, time = 46 ms, mem = 980 KiB, score = 10
测试数据 #4: Accepted, time = 218 ms, mem = 1532 KiB, score = 10
Accepted, time = 279 ms, mem = 1532 KiB, score = 50
代码
include <iostream>
include <cstring>
include <map>
include <queue>
include <algorithm>
using namespace std;
string f[21], t[21], a, b;
map<string, int> ff;
queue<string> q;
int tt = 1;
void bfs(string x)
{
while(!q.empty()) {
string x = q.front();
if(x == b)
return ;
if(ff[x] >= 11) {
q.pop();
continue;
}
for(int i = 1; i < tt; i++) {
int p = x.find(f[i]);
while(p < x.size()) {
string k = "";
k += x.substr(0, p), k += t[i];
k += x.substr(p + f[i].size(), x.size() - p - f[i].size());
if(ff[k] == 0 || ff[x] + 1 < ff[k])
ff[k] = ff[x] + 1, q.push(k);
p = x.find(f[i], p + 1);
}
}
q.pop();
}
}
int main() {
string x, y;
cin >> a >> b;
while(cin >> x >> y)
if(x != y)
f[tt] = x, t[tt++] = y;
q.push(a), ff[a] = 1;
bfs(a);
if(ff[b] == 0)
cout << "NO ANSWER!" << endl;
else
cout << ff[b] - 1 << endl;
return 0;
} -
02015-10-31 16:27:46@
哎,提交了3次。前两次错竟然是忘了把freopen注释掉,哎,郁闷啊。
代码#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<iostream>
using namespace std;
struct node
{
char s[30];
int dep;
} list1[5010],list2[5010];
char a[7][30],b[7][30];
int n;
bool check(char *s1,char *s2)
{
if (strlen(s1)!=strlen(s2)) return false;
for (int i=0;i<strlen(s1);i++)
if (s1[i]!=s2[i]) return false;
return true;
}
bool pan1(char *s,int i,int x)
{
for (int j=i;j<i+strlen(a[x]);j++)
if (s[j]!=a[x][j-i]) return false;
return true;
}
bool pan2(char *s,int i,int x)
{
for (int j=i;j<i+strlen(b[x]);j++)
if (s[j]!=b[x][j-i]) return false;
return true;
}
void bfs()
{
int head1,tail1,head2,tail2,k;
head1=tail1=head2=tail2=1;
while (head1<=tail1 && head2<=tail2)
{
if (list1[head1].dep+list2[head2].dep>10)
{
printf("NO ANSWER!\n");
return ;
}
for (int i=0;i<strlen(list1[head1].s);i++)
for (int j=1;j<=n;j++)
if (pan1(list1[head1].s,i,j))
{
tail1++;
for (k=0;k<i;k++) list1[tail1].s[k]=list1[head1].s[k];
for (int l=0;l<strlen(b[j]);l++,k++) list1[tail1].s[k]=b[j][l];
for (int l=i+strlen(a[j]);l<=strlen(list1[head1].s);l++,k++)
list1[tail1].s[k]=list1[head1].s[l];
list1[tail1].s[k]='\0';
list1[tail1].dep=list1[head1].dep+1;
for (k=1;k<=tail1;k++)
if (check(list1[tail1].s,list2[k].s))
{
printf("%d\n",list1[tail1].dep+list2[k].dep);
return ;
}
}for (int i=0;i<strlen(list2[head2].s);i++)
for (int j=1;j<=n;j++)
if (pan2(list2[head2].s,i,j))
{
tail2++;
for (k=0;k<i;k++) list2[tail2].s[k]=list2[head2].s[k];
for (int l=0;l<strlen(a[j]);l++,k++) list2[tail2].s[k]=a[j][l];
for (int l=i+strlen(b[j]);l<=strlen(list2[head2].s);l++,k++)
list2[tail2].s[k]=list2[head2].s[l];
list2[tail2].s[k]='\0';
list2[tail2].dep=list2[head2].dep+1;
for (k=1;k<=tail1;k++)
if (check(list1[k].s,list2[tail2].s))
{
printf("%d\n",list1[k].dep+list2[tail2].dep);
return ;
}
}
head1++; head2++;
}
printf("NO ANSWER!\n");
}
int main()
{
//freopen("string.in","r",stdin);
//freopen("string.out","w",stdout);
scanf("%s%s",list1[1].s,list2[1].s);
n=1;
while (scanf("%s%s",a[n],b[n])!=EOF) n++;
n--;
list1[1].dep=list2[1].dep=0;
bfs();
return 0;
} -
02015-09-20 20:27:52@
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<set>
using namespace std;
const int MAXN = 50;int n = 1, len1[MAXN], len2[MAXN];
char list1[MAXN][MAXN], list2[MAXN][MAXN];
vector<char> v;
set<string> st;struct Status{
int dep;
char s[100];
}first1, first2;queue<Status> q;
bool check(Status a, Status b){
if(strlen(a.s) != strlen(b.s))
return 0;
for(int i=0; i<strlen(a.s); i++)
if(a.s[i] != b.s[i])
return 0;
return 1;
}void clear(Status &now){
for(int i=0; i<50; i++)
now.s[i] = '\0';
}void check(Status tmp, int a, int b){
//int bri = strlen(tmp.s);
//int tot = min(a+len1[b], bri);
for(int i=a; i<a+len1[b]; i++)
if(list1[b][i-a] != tmp.s[i])
return;
v.clear();
Status now;
clear(now);
for(int i=0; i<a; i++)
v.push_back(tmp.s[i]);
for(int i=0; i<len2[b]; i++)
v.push_back(list2[b][i]);
for(int i=a+len1[b]; i<strlen(tmp.s); i++)
v.push_back(tmp.s[i]);
for(int i=0; i<v.size(); i++)
now.s[i] = v[i];
now.dep = tmp.dep + 1;
if(strlen(now.s) > 20)
return;
if(!st.count(now.s)){
q.push(now);
st.insert(now.s);
}
}void bfs(){
q.push(first1);
while(!q.empty()){
Status now = q.front();
if(now.dep > 10){
printf("NO ANSWER!");
break;
}
if(check(now, first2)){
printf("%d", now.dep);
break;
}
q.pop();
for(int i=0; i<strlen(now.s); i++)
for(int j=1; j<=n; j++)
check(now, i, j);
if(q.empty())
printf("NO ANSWER!");
}
}int main()
{
FILE *fin = fopen("in.txt", "r");
fscanf(fin, "%s%s", first1.s, first2.s);
while(fscanf(fin, "%s%s", list1[n], list2[n]) != EOF){
len1[n] = strlen(list1[n]);
len2[n] = strlen(list2[n]);
n++;
}
n--;
bfs();
return 0;
}
BFS + set判重 -
02015-07-16 16:27:32@
Block code
#include <iostream>
#include <cstring>
#include <map>
#include <queue>
#include <algorithm>
using namespace std;
string f[21], t[21], a, b;
map<string, int> ff;
queue<string> q;
int tt = 1;
void bfs(string x)
{
while(!q.empty()) {
string x = q.front();
if(x == b)
return ;
if(ff[x] >= 11) {
q.pop();
continue;
}
for(int i = 1; i < tt; i++) {
int p = x.find(f[i]);
while(p < x.size()) {
string k = "";
k += x.substr(0, p), k += t[i];
k += x.substr(p + f[i].size(), x.size() - p - f[i].size());
if(ff[k] == 0 || ff[x] + 1 < ff[k])
ff[k] = ff[x] + 1, q.push(k);
p = x.find(f[i], p + 1);
}
}
q.pop();
}
}
int main() {
string x, y;
cin >> a >> b;
while(cin >> x >> y)
if(x != y)
f[tt] = x, t[tt++] = y;
q.push(a), ff[a] = 1;
bfs(a);
if(ff[b] == 0)
cout << "NO ANSWER!" << endl;
else
cout << ff[b] - 1 << endl;
return 0;
}49行精简代码
-
02014-11-05 15:02:24@
const prime:array[1..20] of longint=(2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71);
type info=record
dep:longint;
str:string;
end;var
u:info;
d1,d2:array[0..100000] of string;
i,j,head,tail,tot,dep,v,k:longint;
queue:array[0..100000] of info;
s,s1,s2,ts,tts:string;
f:array[0..10000] of longint;
hash:array[-100000000..100000000] of boolean;
function check(str:string):boolean;
var
h:int64;
i:longint;
begin
h:=0;for i:=1 to length(str) do
begin
h:=((h+ (ord(str[i])-48)*i*i*prime[i]));
if (h>10000000)or(h<-10000000) then
h:=h mod 99999989;
end;
h:=h mod 99999989;
if hash[h] then
exit(false) else
begin
hash[h]:=true;
exit(true);
end;
end;procedure kmp(A,B:string);
var
i,j,m,n:longint;
P:array[0..1000] of longint;
begin
m:=length(B);
n:=length(A);
P[1]:=0;
j:=0;
for i:=2 to n do
begin
while (j>0) and (A[j+1]<>A[i]) do
j:=P[j];
if A[j+1]=A[i] then
j:=j+1;
P[i]:=j;
end;
j:=0;
v:=0;for i:=1 to m do
begin
while (j>0) and (A[j+1]<>B[i]) do
j:=P[j];
if A[j+1]=B[i] then j:=j+1;
if j=n then
begin
inc(v);
f[v]:=i-n+1;
j:=P[j];
end;
end;
end;begin
readln(s);
s1:=copy(s,1,pos(' ',s)-1);
delete(s,1,pos(' ',s));
s2:=s;tot:=0;
while not eof do
begin
inc(tot);
readln(s);
d1[tot]:=copy(s,1,pos(' ',s)-1);
delete(s,1,pos(' ',s));
d2[tot]:=s;
end;head:=1;
tail:=1;
queue[1].str:=s1;
queue[1].dep:=0;
while head<=tail do
begin
u:=queue[head];
dep:=queue[head].dep;
inc(head);
if dep>10 then
break;for j:=1 to tot do
beginkmp(d1[j],u.str);
if v>0 then
begin
for k:=1 to v do
begin
ts:=u.str;
tts:=copy(ts,1,f[k]-1);
delete(ts,1,f[k]+length(d1[j])-1);
tts:=tts+d2[j]+ts;
if check(tts) then
begin
inc(tail);
queue[tail].str:=tts;
queue[tail].dep:=dep+1;
if tts=s2 then
begin
writeln(queue[tail].dep);
halt;
end;
end;
end;
end;
end;
end;
writeln('NO ANSWER!');
end.KMP+hash+bfs
-
02014-10-02 11:40:36@
program p1124;
var
a:array[1..600000]of longint;
x,y,b:array[1..700000]of string[20];
s,s1:string;
i,j,n,he,ti,k:longint;
beginreadln(s);
b[1]:=copy(s,1,pos(' ',s)-1);delete(s,1,pos(' ',s));s1:=s;
while not eof do
begin
inc(n);
readln(s);
x[n]:=copy(s,1,pos(' ',s)-1);delete(s,1,pos(' ',s));y[n]:=s;
end;
he:=0;ti:=1;
while he<=ti do
begin
inc(he);
if b[he]=s1 then begin writeln(a[he]);halt;end;
if a[he]>10 then begin writeln('NO ANSWER!');halt;end;
for i:=1 to n do if pos(x[i],b[he])>0 then begin
inc(ti);a[ti]:=a[he]+1;
b[ti]:=b[he];insert(y[i],b[ti],pos(x[i],b[ti]));
delete(b[ti],pos(x[i],b[ti]),length(x[i]));
s:=b[he];k:=pos(x[i],s);
delete(s,pos(x[i],s),length(x[i]));
if pos(x[i],s)>0 then
begin
inc(ti);
a[ti]:=a[he]+1;b[ti]:=s;
insert(y[i],b[ti],pos(x[i],b[ti]));
delete(b[ti],pos(x[i],b[ti]),length(x[i]));
insert(x[i],b[ti],k);
end;
end;
end;
end.
纯bfs,不加任何优化,AC -
02014-08-20 15:03:23@
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
struct node
{
char s[30];
int d;
}l1[5010],l2[5010];
main()
{
char a[7][30],b[7][30];
int n=1,h1=1,t1=1,h2=1,t2=1,i,j,k,l;
cin>>l1[1].s>>l2[1].s;
while(scanf("%s%s",a[n],b[n])!=EOF)
n++;
n--;
l1[1].d=l2[1].d=0;
while(h1<=t1&&h2<=t2)
{
if(l1[h1].d+l2[h2].d>10)
{
cout<<"NO ANSWER!";
return 0;
}
for(i=0;i<strlen(l1[h1].s);i++)
for(j=1;j<=n;j++)
if(strncmp(l1[h1].s+i,a[j],strlen(a[j]))==0)
{
t1++;
for(k=0;k<i;k++)
l1[t1].s[k]=l1[h1].s[k];
for(l=0;l<strlen(b[j]);l++,k++)
l1[t1].s[k]=b[j][l];
for(l=i+strlen(a[j]);l<=strlen(l1[h1].s);l++,k++)
l1[t1].s[k]=l1[h1].s[l];
l1[t1].s[k]='\0';
l1[t1].d=l1[h1].d+1;
for(k=1;k<=t1;k++)
if(strcmp(l1[t1].s,l2[k].s)==0)
{
cout<<l1[t1].d+l2[k].d;
return 0;
}
}
for(i=0;i<strlen(l2[h2].s);i++)
for(j=1;j<=n;j++)
if(strncmp(l2[h2].s+i,b[j],strlen(b[j]))==0)
{
t2++;
for(k=0;k<i;k++)
l2[t2].s[k]=l2[h2].s[k];
for(l=0;l<strlen(a[j]);l++,k++)
l2[t2].s[k]=a[j][l];
for(l=i+strlen(b[j]);l<=strlen(l2[h2].s);l++,k++)
l2[t2].s[k]=l2[h2].s[l];
l2[t2].s[k]='\0';
l2[t2].d=l2[h2].d+1;
for(k=1;k<=t1;k++)
if(strcmp(l1[k].s,l2[t2].s)==0)
{
cout<<l1[k].d+l2[t2].d;
return 0;
}
}
h1++;
h2++;
}
cout<<"NO ANSWER!";
} -
02014-05-30 21:16:13@
#code
#include <iostream>
#include <string>
#include <map>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;
using namespace __gnu_cxx;
string start,end;
vector<string> w1,w2;
int findstr();
int main(int argc, char** argv) {
cin>>start>>end;
string t1,t2;
while(cin>>t1>>t2)
{
w1.push_back(t1);
w2.push_back(t2);
}
int bfs();
int q=bfs();
if(q==-1) cout<<"NO ANSWER!"<<endl;
else cout<<q<<endl;
return 0;
}
int bfs()
{
map<string,int> l;
l[start]=0;
queue<string> q;
q.push(start);
while(!q.empty())
{string n=q.front();
for(int i=0;i!=w1.size();++i)
{int k=0;
while(k<n.size())
{
int p=n.find(w1[i].c_str(),k);
k+=w1[i].size();
if(p==string::npos) break;
string n1;
for(int j=0;j<p;++j)
n1.push_back(n[j]);
for(int j=0;j<w2[i].size();++j)
n1.push_back(w2[i][j]);
for(int j=p+w1[i].size();j<n.size();++j)
n1.push_back(n[j]);
if(l.count(n1)) continue;
else
l.insert(pair<string,int>(n1,l[n]+1));
if(n1==end) return l[n1];
if(l[n1]>10) return -1;
q.push(n1);
}
}
q.pop();
}
return -1;
}
纯STL实现......
注意这么几点:
有可能出现
abaaaba abcdaba
a b
b d
d e
e f
f g
g c
这样的数据
bfs一定要判重
最后要用一句 return-1;兜底防止无解情况
只有59行哦 -
02014-01-12 19:05:13@
61行单向BFS+hash,快被这题玩死了
-
02013-08-18 23:26:43@
测试数据 #0: Accepted, time = 0 ms, mem = 5760 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 5760 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 5760 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 5760 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 5764 KiB, score = 10
Accepted, time = 0 ms, mem = 5764 KiB, score = 50看代码:
var q:array[1..2,1..10000] of string;{正反向队列}
r:array[1..6,1..2] of string;{转换规则}
step:array[1..2,1..1000] of integer;{答案计数}
a,b:string; {初始状态和目标状态}
h,t:array[1..2] of integer;{两个队列指针}
n,change_number:integer;{规则数,转换结果数}
change_list:array[1..20] of string;
step_now:shortint;{现行步数}
function change(var s:string;a,b:string):boolean;{转换}
var p,p_t:longint;
t:string;
begin
change_number:=0;
p:=pos(a,s);
while p<>0 do
begin
t:=s;
delete(t,p,length(a));
insert(b,t,p);
inc(change_number);
change_list[change_number]:=t;
p_t:=pos(a,copy(s,p+1,length(s)));
if p_t=0 then exit(true);
inc(p,p_t);
end;
if (p=0)and(change_number=0) then exit(false);
exit(true);
end;
procedure add(j{队列号},ste{步数}:shortint;x:string);
begin
inc(t[j]);
step[j,t[j]]:=ste;
q[j,t[j]]:=x;
end;
procedure del(j:shortint;var ste:shortint;var s:string);
begin
inc(h[j]);
s:=q[j,h[j]];
ste:=step[j,h[j]];
end;
function find(j:shortint;s:string):boolean;
var i:longint;
begin
for i:=1 to t[3-j] do{是否在逆向搜索队列中出现}
if s=q[3-j,i] then
begin
writeln(step[3-j,i]+step_now+1);{输出解}
halt;
end;
for i:=1 to t[j] do{是在同向队列重复出现}
if s=q[j,i] then exit(true);
exit(false);
end;
procedure init;{输入初始以及目标,还有规则}
var i:integer;
s:string;
begin
i:=0;
fillchar(h,sizeof(h),0);
fillchar(t,sizeof(t),0);
readln(s);
n:=pos(' ',s);
a:=copy(s,1,n-1);
b:=copy(s,n+1,length(s));
while not(eof) do
begin
inc(i);
readln(s);
n:=pos(' ',s);
r[i,1]:=copy(s,1,n-1);
r[i,2]:=copy(s,n+1,length(s));
end;
n:=i;
add(1,0,a);
add(2,0,b);
end;
procedure dbfs;{双向bfs}
var i,j,k:integer;
temp,str:string;
begin
while (t[1]>h[1])or(t[2]>h[2]) do
for j:=1 to 2 do
begin
del(j,step_now,str);{取出队头元素}
for i:=1 to n do{枚举每种转换规则}
begin
temp:=str;
if change(temp,r[i,j],r[i,3-j]) then
for k:=1 to change_number do
if not find(j,change_list[k]) then
add(j,step_now+1,change_list[k]);
if (step[1,h[1]]>=10)and(step[2,h[2]]>=10) then exit;
end;
end;
end;
begin
init;
dbfs;
writeln('NO ANSWER!');
end. -
02012-10-16 21:35:01@
太棒了,不愧是经典题。
通过一题多解,我不仅学习了hash表还学会了双向广搜。 -
02012-08-08 10:52:01@
├ 测试数据 01:答案正确... (333ms, 25804KB)
├ 测试数据 02:答案正确... (341ms, 25804KB)
├ 测试数据 03:答案正确... (142ms, 25804KB)
├ 测试数据 04:答案正确... (157ms, 25804KB)
├ 测试数据 05:答案正确... (118ms, 25804KB)
---|---|---|---|---|---|---|---|-
Accepted / 100 / 1093ms / 25804KB
双向BFS+天然剪枝