429 - Word Transformation
Moderator: Board moderators
"Word Transformation" (problem 429)
I can't figure out why I get a WA with my solution.
the basic idea is to treat the words as a graph, with edges between 2 words iff they differ by exactly 1 letter. once we tranform it into graph form we can apply the FLoyd Warshall O( n^3 ) algorithm to find the best way of transorming any word to any other word.
[cpp]#include <stdio.h>
#include <string>
#include <vector>
#include <map>
#include <iostream>
using namespace std;
int cnt( string a, string b ){
if ( a.size() != b.size() ) return 0;
int x=0;
for ( int i=0; i<a.size(); i++ )
x+= (a!=b);
return x;
}
int dist[201][201];
map< string, int > ind;
vector<string> w;
int main( void ){
FILE *in=stdin;
int i,j,k,n;
n=0;
while ( 1 ){
string m;
char c[512];
fscanf( in, "%s", c );
m=c;
if ( m=="*" ) break;
ind[ m ]=n;
w.push_back( m );
dist[n][n]=0;
for ( i=0; i<n; i++ ){
k=cnt(w,w[n]);
if ( k==1 ){
dist[n]=dist[n]=1;
// printf( "linkF: %s %s\n", w.c_str(), w[n].c_str() );
}
else
dist[n]=dist[n]=10000001;
}
n++;
}
for ( k=0; k<n; k++ )
for ( i=0; i<n; i++ )
for ( j=0; j<n; j++ )
dist[j]=min( dist[j], dist[i][k]+dist[k][j] );
char a[512],b[512];
while ( 2==fscanf( in, "%s %s", a,b ) ){
string x=a; string y=b;
printf( "%s %s %d\n", a,b,dist[ ind[x] ][ ind[y] ] );
}
return 0;
}[/cpp]
the basic idea is to treat the words as a graph, with edges between 2 words iff they differ by exactly 1 letter. once we tranform it into graph form we can apply the FLoyd Warshall O( n^3 ) algorithm to find the best way of transorming any word to any other word.
[cpp]#include <stdio.h>
#include <string>
#include <vector>
#include <map>
#include <iostream>
using namespace std;
int cnt( string a, string b ){
if ( a.size() != b.size() ) return 0;
int x=0;
for ( int i=0; i<a.size(); i++ )
x+= (a!=b);
return x;
}
int dist[201][201];
map< string, int > ind;
vector<string> w;
int main( void ){
FILE *in=stdin;
int i,j,k,n;
n=0;
while ( 1 ){
string m;
char c[512];
fscanf( in, "%s", c );
m=c;
if ( m=="*" ) break;
ind[ m ]=n;
w.push_back( m );
dist[n][n]=0;
for ( i=0; i<n; i++ ){
k=cnt(w,w[n]);
if ( k==1 ){
dist[n]=dist[n]=1;
// printf( "linkF: %s %s\n", w.c_str(), w[n].c_str() );
}
else
dist[n]=dist[n]=10000001;
}
n++;
}
for ( k=0; k<n; k++ )
for ( i=0; i<n; i++ )
for ( j=0; j<n; j++ )
dist[j]=min( dist[j], dist[i][k]+dist[k][j] );
char a[512],b[512];
while ( 2==fscanf( in, "%s %s", a,b ) ){
string x=a; string y=b;
printf( "%s %s %d\n", a,b,dist[ ind[x] ][ ind[y] ] );
}
return 0;
}[/cpp]
-
- A great helper
- Posts: 284
- Joined: Thu Feb 28, 2002 2:00 am
- Location: Germany
- Contact:
how?
the problem statement states that after the pairs of words there is a EOF
so how can you have multiple input??
assuming its possible to have multiple input how can you distinguish between the end of the pairs of words section and the start of a new data set?
you can answer this by modifying my code for me to handle multiple inputs, if you want![:)](./images/smilies/icon_smile.gif)
so how can you have multiple input??
assuming its possible to have multiple input how can you distinguish between the end of the pairs of words section and the start of a new data set?
you can answer this by modifying my code for me to handle multiple inputs, if you want
![:)](./images/smilies/icon_smile.gif)
-
- A great helper
- Posts: 284
- Joined: Thu Feb 28, 2002 2:00 am
- Location: Germany
- Contact:
forget this
so now I have to worry about blank lines??
forget this problem.
forget this problem.
-
- A great helper
- Posts: 284
- Joined: Thu Feb 28, 2002 2:00 am
- Location: Germany
- Contact:
-
- New poster
- Posts: 24
- Joined: Mon Feb 24, 2003 5:08 pm
429
I can't understand why WA. I use usual Floyd algorithm
[cpp]#include <fstream.h>
#include <string.h>
#define max 201
//#define cin in
//ifstream in("input.txt");
int a[max][max];
int n;
void floyd()
{
int i,j,k;
for (i=0;i<n;i++)
for (j=0;j<n;j++)
for (k=0;k<n;k++)
if (a[j]>a[k]+a[k][j]) a[j]=a[k]+a[k][j];
}
char dic[max][11];
int kol=0;
int bs(char *s)
{
int i;
for (i=0;i<kol;i++)
if (strcmp(dic,s)==0) return i;
return -1;
}
int ok(char *s1,char *s2)
{
int r=0,i;
if (strlen(s1)!=strlen(s2)) return 0;
for (i=0;i<strlen(s1);i++)
if (s1!=s2) r++;
if (r==1) return 1;
return 0;
}
void read(char *s,char *s1,char *s2)
{
int i=0;
while (s>'z' || s<'a') i++;
int j=0;
while (s<='z' && s[i]>='a') {s1[j]=s[i];i++;j++;}
s1[j]=0;
while (s[i]>'z' || s[i]<'a') i++;
j=0;
while (i<strlen(s) && s[i]<='z' && s[i]>='a') {s2[j]=s[i];i++;j++;}
s2[j]=0;
}
int main()
{
int ntest,t;
cin>>ntest;
for (t=0;t<ntest;t++){
if (t!=0) cout<<"\n";
kol=0;n=0;
int i;
cin>>dic[kol];
while (dic[kol][0]!='*')
{
kol++;
cin>>dic[kol];
}
n=kol;
int j;
for (i=0;i<n;i++)
for (j=0;j<n;j++)
if (i!=j) a[i][j]=10000;
else a[i][j]=0;
for (i=0;i<n;i++)
for (j=i+1;j<n;j++)
if (ok(dic[i],dic[j])==1)
{
a[i][j]=1;
a[j][i]=1;
}
char s1[11],s2[11];
char s3[30];
cin.getline(s3,30);
cin.getline(s3,30);
floyd();
while (strlen(s3)!=0)
{
read(s3,s1,s2);
int k1=bs(s1);
int k2=bs(s2);
cout<<s1<<" "<<s2<<" "<<a[k1][k2]<<"\n";
cin.getline(s3,30);
}
}
return 0;
}[/cpp]
[cpp]#include <fstream.h>
#include <string.h>
#define max 201
//#define cin in
//ifstream in("input.txt");
int a[max][max];
int n;
void floyd()
{
int i,j,k;
for (i=0;i<n;i++)
for (j=0;j<n;j++)
for (k=0;k<n;k++)
if (a[j]>a[k]+a[k][j]) a[j]=a[k]+a[k][j];
}
char dic[max][11];
int kol=0;
int bs(char *s)
{
int i;
for (i=0;i<kol;i++)
if (strcmp(dic,s)==0) return i;
return -1;
}
int ok(char *s1,char *s2)
{
int r=0,i;
if (strlen(s1)!=strlen(s2)) return 0;
for (i=0;i<strlen(s1);i++)
if (s1!=s2) r++;
if (r==1) return 1;
return 0;
}
void read(char *s,char *s1,char *s2)
{
int i=0;
while (s>'z' || s<'a') i++;
int j=0;
while (s<='z' && s[i]>='a') {s1[j]=s[i];i++;j++;}
s1[j]=0;
while (s[i]>'z' || s[i]<'a') i++;
j=0;
while (i<strlen(s) && s[i]<='z' && s[i]>='a') {s2[j]=s[i];i++;j++;}
s2[j]=0;
}
int main()
{
int ntest,t;
cin>>ntest;
for (t=0;t<ntest;t++){
if (t!=0) cout<<"\n";
kol=0;n=0;
int i;
cin>>dic[kol];
while (dic[kol][0]!='*')
{
kol++;
cin>>dic[kol];
}
n=kol;
int j;
for (i=0;i<n;i++)
for (j=0;j<n;j++)
if (i!=j) a[i][j]=10000;
else a[i][j]=0;
for (i=0;i<n;i++)
for (j=i+1;j<n;j++)
if (ok(dic[i],dic[j])==1)
{
a[i][j]=1;
a[j][i]=1;
}
char s1[11],s2[11];
char s3[30];
cin.getline(s3,30);
cin.getline(s3,30);
floyd();
while (strlen(s3)!=0)
{
read(s3,s1,s2);
int k1=bs(s1);
int k2=bs(s2);
cout<<s1<<" "<<s2<<" "<<a[k1][k2]<<"\n";
cin.getline(s3,30);
}
}
return 0;
}[/cpp]
-
- Learning poster
- Posts: 94
- Joined: Wed Jul 31, 2002 12:44 pm
- Location: Dacca, Bangladesh
- Contact:
your floyd algorithm is wrong here...the intermediate node selection loop (k=0; k<... in your code) should be the outer most loop and also you are not creating new paths where direct edge is not possible.
so modifying a little your floyd algo should be ok[cpp]void floyd()
{
int i,j,k;
for (k=0;k<n;k++)
for (i=0;i<n;i++)
for (j=0;j<n;j++)
if (a[j]==0 || a[j]>a[k]+a[k][j])
a[j]=a[k]+a[k][j];
}
[/cpp]
greetings![:wink:](./images/smilies/icon_wink.gif)
so modifying a little your floyd algo should be ok[cpp]void floyd()
{
int i,j,k;
for (k=0;k<n;k++)
for (i=0;i<n;i++)
for (j=0;j<n;j++)
if (a[j]==0 || a[j]>a[k]+a[k][j])
a[j]=a[k]+a[k][j];
}
[/cpp]
greetings
![:wink:](./images/smilies/icon_wink.gif)
Istiaque Ahmed [the LA-Z-BOy]
-
- New poster
- Posts: 24
- Joined: Mon Feb 24, 2003 5:08 pm
-
- Learning poster
- Posts: 94
- Joined: Wed Jul 31, 2002 12:44 pm
- Location: Dacca, Bangladesh
- Contact:
429 - Word Transformation
I try to solve this problem. But i am getting RTE.
Please help me with some multiple inputs.
Thanks.
Please help me with some multiple inputs.
Thanks.
-
- New poster
- Posts: 1
- Joined: Tue Dec 09, 2003 11:54 am
429 - WA
Hello guys,
I sent the following code and i got WA, is there anyone has any idea why?
[cpp]
#include <cstdio>
#include <vector>
#include <iostream>
#include <string>
#include <cstring>
#include <queue>
using namespace std;
typedef struct{
char words[11];
bool visited;
int dist;
vector<int> neigh;
}Word;
typedef struct{
Word wlist[10][200];
int size[10];
}WList;
int search_path(WList *wl, int len, int spos, int tpos){
int pos;
int count;
int path = 1;
vector<int>::iterator en;
vector<int>::iterator bg;
bool found = false;
queue<int> q;
q.push(spos);
for(int i=0;i<200;i++) wl->wlist[len].visited = false;
wl->wlist[len][spos].visited = true;
wl->wlist[len][spos].dist = 0;
while(!q.empty()){
pos = q.front();
q.pop();
en = wl->wlist[len][pos].neigh.end();
bg = wl->wlist[len][pos].neigh.begin();
for(vector<int>::iterator it=bg;it!=en;it++){
if(!wl->wlist[len][*it].visited){
path=wl->wlist[len][*it].dist = wl->wlist[len][pos].dist+1;
count = 0;
for(int i=0;i<=len;i++){
if(wl->wlist[len][tpos].words == wl->wlist[len][*it].words) count++;
}
if( count == (len+1) ) {
found = true;
goto outerloop;
}
q.push(*it);
wl->wlist[len][*it].visited = true;
}
}
}
outerloop:
if(found) return path;
return 0;
}
int main(int argc,char **argv){
char input[50];
char temp[50];
WList dict;
size_t len;
string output = "";
char *pin;
char src[11],target[11];
for(int i=0;i<10;i++) dict.size = 0;
while(true){
fgets(input,50,stdin);
if(strlen(input) > 1)
input[strlen(input)-1] = '\0';
if(strcmp(input,"*") == 0) break;
len = strlen(input);
int dist;
if(dict.size[len-1] > 0){
strncpy(dict.wlist[len-1][dict.size[len-1]].words,input,len);
for(int j=0;j<=dict.size[len-1];j++){
int count = 0;
for(int k=0;k<len;k++)
if(dict.wlist[len-1][j].words[k] != input[k]) count++;
if(count == 1){
dict.wlist[len-1][j].neigh.push_back(dict.size[len-1]);
dict.wlist[len-1][dict.size[len-1]].neigh.push_back(j);
}
}
dict.size[len-1]++;
}
else{
strncpy(dict.wlist[len-1][0].words,input,len);
dict.size[len-1]++;
}
}
while(true){
fgets(input,50,stdin);
if(feof(stdin)) break;
if(strlen(input) > 1) input[strlen(input)-1] = '\0';
sscanf(input,"%s %s",src,target);
size_t srclen = strlen(src);
int srcpos = 0;
int tarpos = 0;
for(int j=0;j<dict.size[srclen-1];j++){
if(strcmp(dict.wlist[srclen-1][j].words,src) == 0){
srcpos = j;
break;
}
}
for(int j=0;j<dict.size[srclen-1];j++){
if(strcmp(dict.wlist[srclen-1][j].words,target) == 0){
tarpos = j;
break;
}
}
int bpath = search_path(&dict,srclen-1,srcpos,tarpos);
sprintf(temp,"%s %s %d\n",src,target,bpath);
output += temp;
}
cout << output;
}
Thank you in advance
[/cpp]
I sent the following code and i got WA, is there anyone has any idea why?
[cpp]
#include <cstdio>
#include <vector>
#include <iostream>
#include <string>
#include <cstring>
#include <queue>
using namespace std;
typedef struct{
char words[11];
bool visited;
int dist;
vector<int> neigh;
}Word;
typedef struct{
Word wlist[10][200];
int size[10];
}WList;
int search_path(WList *wl, int len, int spos, int tpos){
int pos;
int count;
int path = 1;
vector<int>::iterator en;
vector<int>::iterator bg;
bool found = false;
queue<int> q;
q.push(spos);
for(int i=0;i<200;i++) wl->wlist[len].visited = false;
wl->wlist[len][spos].visited = true;
wl->wlist[len][spos].dist = 0;
while(!q.empty()){
pos = q.front();
q.pop();
en = wl->wlist[len][pos].neigh.end();
bg = wl->wlist[len][pos].neigh.begin();
for(vector<int>::iterator it=bg;it!=en;it++){
if(!wl->wlist[len][*it].visited){
path=wl->wlist[len][*it].dist = wl->wlist[len][pos].dist+1;
count = 0;
for(int i=0;i<=len;i++){
if(wl->wlist[len][tpos].words == wl->wlist[len][*it].words) count++;
}
if( count == (len+1) ) {
found = true;
goto outerloop;
}
q.push(*it);
wl->wlist[len][*it].visited = true;
}
}
}
outerloop:
if(found) return path;
return 0;
}
int main(int argc,char **argv){
char input[50];
char temp[50];
WList dict;
size_t len;
string output = "";
char *pin;
char src[11],target[11];
for(int i=0;i<10;i++) dict.size = 0;
while(true){
fgets(input,50,stdin);
if(strlen(input) > 1)
input[strlen(input)-1] = '\0';
if(strcmp(input,"*") == 0) break;
len = strlen(input);
int dist;
if(dict.size[len-1] > 0){
strncpy(dict.wlist[len-1][dict.size[len-1]].words,input,len);
for(int j=0;j<=dict.size[len-1];j++){
int count = 0;
for(int k=0;k<len;k++)
if(dict.wlist[len-1][j].words[k] != input[k]) count++;
if(count == 1){
dict.wlist[len-1][j].neigh.push_back(dict.size[len-1]);
dict.wlist[len-1][dict.size[len-1]].neigh.push_back(j);
}
}
dict.size[len-1]++;
}
else{
strncpy(dict.wlist[len-1][0].words,input,len);
dict.size[len-1]++;
}
}
while(true){
fgets(input,50,stdin);
if(feof(stdin)) break;
if(strlen(input) > 1) input[strlen(input)-1] = '\0';
sscanf(input,"%s %s",src,target);
size_t srclen = strlen(src);
int srcpos = 0;
int tarpos = 0;
for(int j=0;j<dict.size[srclen-1];j++){
if(strcmp(dict.wlist[srclen-1][j].words,src) == 0){
srcpos = j;
break;
}
}
for(int j=0;j<dict.size[srclen-1];j++){
if(strcmp(dict.wlist[srclen-1][j].words,target) == 0){
tarpos = j;
break;
}
}
int bpath = search_path(&dict,srclen-1,srcpos,tarpos);
sprintf(temp,"%s %s %d\n",src,target,bpath);
output += temp;
}
cout << output;
}
Thank you in advance
![:lol:](./images/smilies/icon_lol.gif)
Hi Juli,
I might be wrong but I don't think you are handling this program as a 'multiple input problem'. If you look closely beside the probelm name you will see a blue tick. It indicates multiple input form.
If you are a newcomer then you will find this useful.
Multiple input fomat:
N
CASE 1
CASE 2
CASE N
-- where N indicates the number of test cases.
The consecutive outputs are seperated by a blank line.
![:wink:](./images/smilies/icon_wink.gif)
I might be wrong but I don't think you are handling this program as a 'multiple input problem'. If you look closely beside the probelm name you will see a blue tick. It indicates multiple input form.
If you are a newcomer then you will find this useful.
Multiple input fomat:
N
CASE 1
CASE 2
CASE N
-- where N indicates the number of test cases.
The consecutive outputs are seperated by a blank line.
![:wink:](./images/smilies/icon_wink.gif)
-
- New poster
- Posts: 2
- Joined: Fri Mar 07, 2003 9:14 am
- Location: republic of korea
problem 429 WA help me~
i used floyd to search for the shortest transformation..
but always got WA..
are there tricky inputs ??
please help me solving problem!!
code is attached below..
[cpp]
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
#define INFINITY 1000000
bool Trans(char *a, char *b)
{
int len,i,cnt=0;
len=strlen(a);
for(i=0;i<len;i++)
if(a!=b) cnt++;
return (cnt==1?true:false);
}
void main()
{
char dic[210][15],word1[15],word2[15];
int map[210][210]={0,};
int wordCnt=0,i,j,k,caseno;
cin>>caseno;
while(caseno--){
while(cin>>dic[wordCnt] && dic[wordCnt][0]!='*') wordCnt++;
for(i=0;i<210;i++)
for(j=0;j<210;j++)
if(i!=j) map[j]=INFINITY;
for(i=0;i<wordCnt;i++)
for(j=i+1;j<wordCnt;j++)
if(strlen(dic)==strlen(dic[j]) && Trans(dic,dic[j]))
map[j]=map[j]=1;
for(k=0;k<wordCnt;k++)
for(i=0;i<wordCnt;i++)
for(j=0;j<wordCnt;j++)
if(map[k]+map[k][j]<map[j])
map[j]=map[i][k]+map[k][j];
while(cin>>word1>>word2){
// if(word1[0]=='0') break;
for(i=0;strcmp(dic[i],word1) && i<wordCnt;i++);
for(j=0;strcmp(dic[j],word2) && j<wordCnt;j++);
cout<<word1<<" "<<word2<<" "<<map[i][j]<<endl;
}
wordCnt=0;
}
}
[/cpp]
but always got WA..
are there tricky inputs ??
please help me solving problem!!
code is attached below..
[cpp]
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
#define INFINITY 1000000
bool Trans(char *a, char *b)
{
int len,i,cnt=0;
len=strlen(a);
for(i=0;i<len;i++)
if(a!=b) cnt++;
return (cnt==1?true:false);
}
void main()
{
char dic[210][15],word1[15],word2[15];
int map[210][210]={0,};
int wordCnt=0,i,j,k,caseno;
cin>>caseno;
while(caseno--){
while(cin>>dic[wordCnt] && dic[wordCnt][0]!='*') wordCnt++;
for(i=0;i<210;i++)
for(j=0;j<210;j++)
if(i!=j) map[j]=INFINITY;
for(i=0;i<wordCnt;i++)
for(j=i+1;j<wordCnt;j++)
if(strlen(dic)==strlen(dic[j]) && Trans(dic,dic[j]))
map[j]=map[j]=1;
for(k=0;k<wordCnt;k++)
for(i=0;i<wordCnt;i++)
for(j=0;j<wordCnt;j++)
if(map[k]+map[k][j]<map[j])
map[j]=map[i][k]+map[k][j];
while(cin>>word1>>word2){
// if(word1[0]=='0') break;
for(i=0;strcmp(dic[i],word1) && i<wordCnt;i++);
for(j=0;strcmp(dic[j],word2) && j<wordCnt;j++);
cout<<word1<<" "<<word2<<" "<<map[i][j]<<endl;
}
wordCnt=0;
}
}
[/cpp]
aaa
429 RTE!!
hi !
I don't see the reason I'm gettin' RTE
anyone do?
I don't see the reason I'm gettin' RTE
anyone do?
Code: Select all
#include <stdio.h>
#include <string.h>
#define MAX 201
#define LIMIT 11
char library[MAX][LIMIT];
char check[MAX][LIMIT];
char current[LIMIT];
int how;
int j = 0;
int d = 0;
int main(void)
{
scanf("%d",&how);
for(int a = 0; a < how; a++)
{
int i = 0;
while(scanf("%s",&library[i]))
{
if(library[i][0]=='*')
break;
i++;
}
i--;
while(scanf("%s%s",&check[j],&check[j+1])==2)
{
j+=2;
}
for(d = 0; d < j; d++){
int quantity = 0;
for(int a = 0; a < LIMIT; a++)
current[a] = check[d][a];
for(int b = 0; b <= i; b++)
{
int count = 0;
for(int c = 0; c < LIMIT; c++)
if(current[c]!=library[b][c])
count++;
if(count==1)
{
int i;
for(i = 0; i < strlen(library[b]); i++)
current[i] = library[b][i];
for(i = 0; i < strlen(current); i++)
library[b][i] = '\0';
quantity++;
}
}
printf("%s %s %d\n",check[d],check[d+1],quantity);
d++;
}
}
return 0;
}
keep it real!