Thanks a lot brianfry, I missed that optimization.If you do that inside the BFS you are repeating a lot of comparisons.
429 - Word Transformation
Moderator: Board moderators
-
PromeNabid
- New poster
- Posts: 21
- Joined: Mon Jun 18, 2012 12:52 am
- Location: Dhaka, Bangladesh.
- Contact:
Re: 429 - Word Transformation
-
richatibrewal
- New poster
- Posts: 49
- Joined: Mon Jun 16, 2014 7:40 pm
Re: 429 - Word Transformation
Hii, I am getting WA for this problem. Following is my code :-
Code: Select all
#include<cstdio>
#include<string>
#include<map>
#include<iostream>
#include<vector>
#include<climits>
#include<queue>
#include<sstream>
#define MAXLEN 210
using namespace std;
map<string,int> mp;
vector<vector<int> > graph;
int dist[MAXLEN];
bool visited[MAXLEN];
int find_diff(string a,string b)
{
int d=0,i,j;
if(a.size()!=b.size())
return -1;
for(i=0;i<a.size();i++)
{
if(a[i]!=b[i])
d++;
}
return d;
}
void make_graph(int n,int m)
{
graph[n].push_back(m);
graph[m].push_back(n);
}
void shortest_path(int a,int b)
{
int i,u,v;
dist[a]=0;
queue<int> q;
q.push(a);
while(!q.empty())
{
u=q.front();
visited[u]=true;
q.pop();
for(i=0;i<graph[u].size();i++)
{
v=graph[u][i];
if(dist[v]>dist[u]+1 && !visited[v])
{
dist[v]=dist[u]+1;
// printf("%d %d %d\n",u,v,dist[v]);
q.push(v);
}
}
}
}
int main()
{
int i,j,l,n,node,diff,x,y;
string str,a,b;
scanf("%d",&n);
getchar();
getchar();
while(n--)
{
node=0;
vector<int > v;
graph.push_back(v);
while(1)
{
cin>>str;
if(str[0]=='*')
break;
if(!mp[str])
mp[str]=++node;
map<string,int>::iterator it;
i=0;
vector<int > v;
graph.push_back(v);
// make_graph(0,node);
for(it=mp.begin();it!=mp.end();it++)
{
i++;
diff=find_diff(it->first,str);
if(diff==1)
make_graph(i,node);
}
}
/* map<string,int>::iterator it;
for(it=mp.begin();it!=mp.end();it++)
cout<<it->first<<" "<<it->second<<endl;
for(i=0;i<graph.size();i++)
{
printf("%d---",i);
for(j=0;j<graph[i].size();j++)
printf("%d ",graph[i][j]);
printf("\n");
}*/
getchar();
//printf("yoo");
getline(cin,str);
//cout<<str;
while(!str.empty())
{
// printf("ff");
for(i=0;i<=node;i++)
{
dist[i]=INT_MAX;
visited[i]=false;
}
stringstream ss(str);
ss>>a>>b;
x=mp[a];
y=mp[b];
// printf("\n%d %d",x,y);
shortest_path(x,y);
cout<<a<<" "<<b<<" "<<dist[y]<<endl;
getline(cin,str);
}
if(n!=0)
printf("\n");
mp.clear();
graph.clear();
}
return 0;
}
429-Word Tranformation
getting wa...
tried some critical input..
tried some critical input..
Code: Select all
#include<bits/stdc++.h>
using namespace std;
map<string,int>visited;
map<string,int>level;
int bfs(string src,string des,map< string,vector<string> >Graph)
{
queue<string>Q;
Q.push(src);
visited[src]=0;
level[src]=0;
while(!Q.empty())
{
string u=Q.front();
for(int i=0;i<Graph[u].size();i++)
{
string v=Graph[u][i];
if(!visited[v])
{
level[v]=level[u]+1;
visited[v]=1;
Q.push(v);
}
}
Q.pop();
}
return level[des];
}
bool compare(string s1,string s2)
{
int count=0;
for(int i=0;i<max(s1.size(),s2.size());i++)
{
if(s1[i]!=s2[i])
{
if(count>1) break;
count++;
}
}
if(count==1) return true;
else return false;
}
int main()
{
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
int TestCase,cnt=0;
cin>>TestCase;
while(TestCase--)
{
if(cnt>0) cout<<endl;
map< string,vector<string> >Graph;
vector<string>v;
string s;
cin>>s;
while(s[0]!='*')
{
if(s[0]=='*') break;
for(int i=0;i<v.size();i++)
{
if(compare(s,v[i]))
{
Graph[s].push_back(v[i]);
Graph[v[i]].push_back(s);
visited[s]=0;
visited[v[i]]=0;
level[s]=0;
level[v[i]]=0;
}
}
v.push_back(s);
cin>>s;
}
string s1,s2;
string line;
getline(cin,line);
getline(cin,line);
while(line !="")
{
int pos=0;
pos=line.find(" ");
s1=line.substr(0,pos);
s2=line.substr(pos+1,line.size());
cout<<s1<<" "<<s2<<" "<<bfs(s1,s2,Graph)<<endl;
if(!getline(cin,line))
break;
}
cnt++;
}
return 0;
}
Re: 429 - Word Transformation Getting WA. Please help
Code: Select all
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <cstring>
#include <map>
using namespace std;
map<string, int> M;
string source, destination;
int dist[300];
int visited[300];
vector<string> P[300];
vector<int> G[300];
bool compare(string s, string str){
int times = 0;
for(int i = 0; i < s.size(); i++){
if(s[i] != str[i])
++times;
}
if(times == 1)
return true;
else
return false;
}
int BFS(int source, int destination){
queue<int> q;
// cout << source << " " << destination << endl;
dist[source] = 0;
visited[source] = 1;
q.push(source);
while(!q.empty()){
int u = q.front();
q.pop();
if(u == destination)
return dist[u];
for(int i = 0; i < G[u].size(); i++){
int v = G[u][i];
if(visited[v] == 0){
visited[v] = 1;
dist[v] = dist[u] + 1;
q.push(v);
if(v == destination)
return dist[v];
}
}
}
return 0;
}
int main()
{
int t;
cin >> t;
getchar();
for(int i = 1; i <= t; i++){
for(int h = 0; h < 201; h++)
{
G[h].clear();
P[h].clear();
}
if(i > 1)
cout << endl;
memset(visited, 0, sizeof(visited));
memset(dist, 0, sizeof(dist));
M.clear();
string s;
char c[20];
int cnt = 0;
getchar();
while(gets(c)){
if(c[0] == '*')
break;
string s(c);
int len = s.size();
if(M[s] == 0){
M[s] = cnt + 1;
cnt += 1;
P[len].push_back(s);
}
for(int k = 0; k < P[len].size(); k++){
string str = P[len][k];
if(compare(s, str)){
G[M[s]].push_back(M[str]);
G[M[str]].push_back(M[s]);
//cout << s << " gg " << str;
}
}
}
while(gets(c)){
if(c[0] == '\0')
break;
int l = strlen(c);
bool flag = false;
string d = "", s = "";
for(int i = 0; i < l; i++){
if(c[i] == ' ')
flag = true;
else if(flag)
d += c[i];
else
s += c[i];
}
int ans;
source = s; destination = d;
if(s.size() != d.size())
ans = 0;
else
ans = BFS(M[source], M[destination]);
cout << s << " " << d << " " << ans << endl;
memset(visited, 0, sizeof(visited));
memset(dist, 0, sizeof(dist));
}
}
return 0;
}
Last edited by brianfry713 on Mon Apr 13, 2015 11:45 pm, edited 1 time in total.
Reason: Added code block
Reason: Added code block
Re: 429 - Word Transformation WA helpppppppp
Code: Select all
#include <cstdio>
#include <map>
#include <vector>
#include <queue>
#include <iostream>
#include <sstream>
#include <set>
using namespace std;
struct word
{
string pal;
int step;
};
int main()
{
int n;
scanf("%d",&n);
string dic;
cin.ignore();
getline(cin,dic);
bool primera=true;
while(n--)
{
bool com=true;
map<string, set<string> > ma;
map<string,bool> visi;
set<string> v;
if(!primera)
printf("\n");
primera=false;
while(getline(cin,dic) && dic.size()!=0)
{
if(dic=="*")
com=false;
if(com)
{
set<string>:: iterator it=v.begin();
visi[dic]=false;
for(;it!=v.end();it++)
{
if(dic.size()==(*it).size())
{
int c=0;
for(int j=0;j<dic.size() && c<2;j++)
{
if(dic[j] != (*it)[j])
c++;
}
if(c==1)
{
ma[dic].insert((*it));
ma[(*it)].insert(dic);
}
}
}
v.insert(dic);
}
else
{
istringstream S(dic);
string a,b;
S>>a>>b;
queue<word> Q;
word u;
u.pal=a;
u.step=0;
Q.push(u);
visi[a]=true;
while(!Q.empty())
{
u=Q.front();
if(u.pal==b)
{
//cout<<a<<" "<<b<<" "<<u.step<<endl;
printf("%s %s %d\n",a.c_str(),b.c_str(),u.step);
break;
}
Q.pop();
set<string> ::iterator it=ma[u.pal].begin();
for(;it!=ma[u.pal].end();it++)
{
word v;
v.pal=(*it);
v.step=u.step+1;
if(visi[v.pal]==false)
{
Q.push(v);
visi[v.pal]=true;
}
}
}
}
}
}
}
Last edited by brianfry713 on Fri Jun 19, 2015 6:30 am, edited 1 time in total.
Reason: Added code blocks
Reason: Added code blocks
Re: 429 - Word Transformation
Code: Select all
#include <cstdio>
#include <map>
#include <vector>
#include <queue>
#include <iostream>
#include <sstream>
#include <set>
using namespace std;
struct word
{
string pal;
int step;
};
int main()
{
int n;
scanf("%d",&n);
string dic;
cin.ignore();
getline(cin,dic);
bool primera=true;
while(n--)
{
bool com=true;
map<string, set<string> > ma;
map<string,bool> visi;
set<string> v;
if(!primera)
printf("\n");
primera=false;
while(getline(cin,dic) && dic.size()!=0)
{
if(dic=="*")
com=false;
if(com)
{
set<string>:: iterator it=v.begin();
visi[dic]=false;
for(;it!=v.end();it++)
{
if(dic.size()==(*it).size())
{
int c=0;
for(int j=0;j<dic.size() && c<2;j++)
{
if(dic[j] != (*it)[j])
c++;
}
if(c==1)
{
ma[dic].insert((*it));
ma[(*it)].insert(dic);
}
}
}
v.insert(dic);
}
else
{
istringstream S(dic);
string a,b;
S>>a>>b;
queue<word> Q;
word u;
u.pal=a;
u.step=0;
Q.push(u);
visi[a]=true;
while(!Q.empty())
{
u=Q.front();
if(u.pal==b)
{
//cout<<a<<" "<<b<<" "<<u.step<<endl;
printf("%s %s %d\n",a.c_str(),b.c_str(),u.step);
break;
}
Q.pop();
set<string> ::iterator it=ma[u.pal].begin();
for(;it!=ma[u.pal].end();it++)
{
word v;
v.pal=(*it);
v.step=u.step+1;
if(visi[v.pal]==false)
{
Q.push(v);
visi[v.pal]=true;
}
}
}
}
}
}
}
Re: 429 - Word Transformation
Hi,
I think I almost have a solution (in Java). However, it states Runtime Error. I've been looking at my code for quite a while now and can't find the problem.
I think I almost have a solution (in Java). However, it states Runtime Error. I've been looking at my code for quite a while now and can't find the problem.
Code: Select all
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
/**
* Created by nander on 10-11.
*/
public class Main {
public static boolean neighbours(String w1, String w2)
{
int diff = 0;
if(w1.length() != w2.length()) {
return false;
}
for(int i=0;i<w1.length();i++)
if(w1.charAt(i) != w2.charAt(i)) {
diff++;
if (diff > 1) {
return false;
}
}
return true;
}
public static void main (String[] args) {
Scanner s = new Scanner(System.in);
int cases = s.nextInt();
while (cases-- > 0) {
String word;
HashMap<String,Integer> dict = new HashMap<>();
int N=0;
while( !(word = s.next()).equals( "*"))
{
dict.put(word,N);
N++;
}
boolean[][] conversions = new boolean[N][N];
for(String word1 : dict.keySet())
for(String word2 : dict.keySet())
if(neighbours(word1,word2))
{
conversions[dict.get(word1)][dict.get(word2)] = true;
}
String line;
s.nextLine();
while(!( line = s.nextLine()).equals(""))
{
String[] l = line.split(" ");
String word1 = l[0];
String word2 = l[1];
int w1 = dict.get(word1);
int w2 = dict.get(word2);
int[] ans = new int[N+1];
Queue<Integer> Q = new LinkedList<>();
Q.offer(w1);
int final_ans = -1;
if( w1 == w2)
final_ans = 0;
for(int i=0;i<N;i++)
ans[i]=-1;
while(!Q.isEmpty())
{
int el = Q.poll();
for(int ii=0;ii<N; ii++)
{
if(conversions[el][ii] && ans[ii]==-1 )
{
ans[ii] = ans[el]+ 1;
Q.offer(ii);
if(ii == w2) {
final_ans = ans[ii];
break;
}
}
}
if(final_ans != -1)
break;
}
System.out.println(word1+" "+ word2+ " "+final_ans);
}
if(cases > 0)
System.out.println("");
}
}
}-
anacharsis
- Learning poster
- Posts: 69
- Joined: Mon Feb 09, 2015 1:56 am
Re: 429 - Word Transformation
Some I/O
In:
AC out:
In:
Code: Select all
1
axe
axi
bxi
cxi
dxi
dli
dlx
dls
cls
clx
*
axe axi
axe clx
axi cls
axi dli
dli cls
cxi cls
Code: Select all
axe axi 1
axe clx 5
axi cls 4
axi dli 2
dli cls 2
cxi cls 4