285 - Crosswords

[spider_6765]

why am i getting TLE? how can I improve the timing?

Code: Select all

#include<stdio.h>
#include<string.h>
#define MAX 1000

void place();
void init(int w,int h);
void check();

char array[1000][1000],word[1000][1000],dir[1000];
int point[1000][2],num_of_words,w,h;

int main(){
	//freopen("input.txt","r",stdin);	
	int i;	
	while(scanf("%s %d %d %c",word[0],&point[0][1],&point[0][0],&dir[0])==4){
		for(i=1;;i++){
			scanf("%s",word[i]);
			if(!strcmp(word[i],"#"))
				break;
			scanf("%d %d %c",&point[i][1],&point[i][0],&dir[i]);		
		}					
		num_of_words=i;		
		scanf("%d%d",&w,&h);
		init(w,h);
		place();		
		check();		
	}	
	return 0;
}

void place(){
	int i,j,l,k;
	for(i=0;i<num_of_words;i++){
		l=strlen(word[i]);
		if(dir[i]=='r'){
			for(j=0,k=point[i][1];j<l;j++,k++){
				array[point[i][0]][k]=word[i][j];
			}		
		}
		else if(dir[i]=='l'){
			for(j=0,k=point[i][1];j<l;j++,k--){
				array[point[i][0]][k]=word[i][j];			
			}					
		}
		else if(dir[i]=='d'){
			for(j=0,k=point[i][0];j<l;j++,k++){
				array[k][point[i][1]]=word[i][j];			
			}		
		}	
		
		else if(dir[i]=='u'){
			for(j=0,k=point[i][0];j<l;j++,k--){
				array[k][point[i][1]]=word[i][j];			
			}		
		}	
	}
}

void init(int w,int h){
	int i,j;
	for(i=1;i<=h;i++)
		for(j=1;j<=w;j++)
			array[i][j]=' ';	
}
void check(){
	int i,j,k,l,wordflag=0,flag=0;
	char temp[100000],temp2[100000];	
	getchar();
	gets(temp);
	
	for(i=0,j=0;i<=strlen(temp);i++){
		if(temp[i]!=' '&&temp[i]!='$'){
			temp[j++]=temp[i];
		}		
	}
	for(i=1,k=0;i<=h;i++){
		for(j=1;j<=w;j++){
			if(array[i][j]!=' '){
				temp2[k++]=array[i][j];
			}		
		}
	}	
	temp2[k]='\0';
	
	if(strlen(temp)!=strlen(temp2)){	
		printf("The solution is incorrect.\n");
		return;
	}
	for(i=0;i<strlen(temp);i++){
		if(temp[i]!=temp2[i]){
			printf("The solution is incorrect.\n");
			return;
		}
	}		
	
	for(i=1;i<=h;i++){
		if(array[i][w]!=' '){
			flag=1;
			break;		
		}
	}
	if(flag==1){
		flag=0;
		for(i=1;i<=w;i++){
			if(array[h][i]!=' '){
				flag=1;
				break;		
			}
		}	
	}
	if(flag==1)
		printf("The solution is correct.\n");
	else 
		printf("The solution is incorrect.\n");
}

[metaphysis]

Weird problem statement.
1)Extra spaces may inserted before a row in the solution.
2)Spaces may removed from the start/end/middle of a row in the solution.
the minimal width and height means the right margin and bottom margin of crossword counting from (1,1).
for examle:

Code: Select all

alas 2 1 r
#
4
1
alas$

the corresponding crossword is(* is space):
*alas
the minimal width of this crossword is 5, not 4, so the solution is incorrect.