Problem 1002, why does my program get WA?
I write the code and the output has the same output with the sample
output. Is there a test case for my program, so I can get the bug?
Thank You!
This is the source code:
/* @judge_id: 15467RK 1002 C */
#include <stdio.h>
#include <string.h>
#define MAX 108
#define MAX2 307208
#define MAX3 50000
#define MAX4 51
struct path {
int id;
int nextpath;
} path[MAX3];
char number[MAX];
char temp[MAX4];
char dictionary[MAX2];
int pdictionary[MAX3+1];
int tdictionary;
int numlen;
int last;
int bisa[26][100];
int tempbisa[100];
char tempbisaok[100];
int ttempbisa;
int tbisa[26];
int tpath;
int nextpath[100];
int i,j,k,l,m,n;
int min;
int result[MAX];
int tempresult[MAX];
char pre[10][3]={
{'o','q','z'},
{'i','j'},
{'a','b','c'},
{'d','e','f'},
{'g','h'},
{'k','l'},
{'m','n'},
{'p','r','s'},
{'t','u','v'},
{'w','x','y'}
};
int tpre[10]={
3,2,3,3,2,2,2,3,3,3
};
void cari (int idx,int tword) {
int i,j;
if (min!=MAX && min<=tword) return;
if (nextpath[idx]!=-1) {
i=nextpath[idx];
while (i!=-1) {
if (pdictionary[path[i].id+1]-pdictionary[path
[i].id]+idx==numlen) {
if (min==MAX || min>tword) {
for (j=0;j<tword-1;j++)
result[j]=tempresult
[j];
result[tword-1]=path[i].id;
min=tword;
return;
}
} else if (pdictionary[path[i].id+1]-
pdictionary[path[i].id]+idx<numlen) {
tempresult[tword-1]=path[i].id;
cari (pdictionary[path[i].id+1]-
pdictionary[path[i].id]+idx,tword+1);
}
i=path[i].nextpath;
}
}
}
void main () {
while (scanf ("%s",number)==1 && number[0]!='-') {
last=0;
scanf ("%d",&tdictionary);
pdictionary[0]=last;
for (i=0;i<26;i++) tbisa[i]=0;
numlen=j=strlen (number);
for (i=0;i<j;i++) {
for (k=0;k<tpre[number[i]-'0'];k++) {
l=pre[number[i]-'0'][k]-'a';
bisa[l][tbisa[l]++]=i;
}
nextpath[i]=-1;
}
tpath=0;
for (i=0;i<tdictionary;i++) {
scanf ("%s",&dictionary[last]);
ttempbisa=0;
l=0;
for (j=0;dictionary[last+j];j++) {
m=dictionary[last+j]-'a';
if (ttempbisa || !l) {
for (k=0;k<tbisa[m];k++) {
if (l) {
for
(n=0;n<ttempbisa;n++) {
if
(tempbisa[n]==bisa[m][k]) {
tempbisaok[n]=1;
}
}
} else {
tempbisaok
[ttempbisa]=1;
tempbisa
[ttempbisa++]=bisa[m][k];
l=1;
}
}
}
for (n=ttempbisa-1;n>=0;n--) {
if (tempbisaok[n]) {
tempbisa[n]++;
tempbisaok[n]=0;
} else {
tempbisa[n]=tempbisa[-
-ttempbisa];
}
}
}
for (k=0;k<ttempbisa;k++) {
if (nextpath[tempbisa[k]-j]==-1) {
nextpath[tempbisa[k]-j]=tpath;
} else {
l=nextpath[tempbisa[k]-j];
while (path[l].nextpath!=-1)
l=path[l].nextpath;
path[l].nextpath=tpath;
}
path[tpath].id=i;
path[tpath].nextpath=-1;
tpath++;
}
last=j+last;
pdictionary[i+1]=last;
}
min=MAX;
cari (0,1);
if (min==MAX) puts ("No solution.");
else {
for (i=0;i<min;i++) {
for (j=pdictionary[result
[i]];j<pdictionary[result[i]+1];j++)
printf ("%c",dictionary[j]);
printf (" ");
}
puts ("");
}
}
}
/* @end_of_source_code */