You are given a grid denoting a simple crossword, consisting of the characters '#', 'r', 'c', 'b' and '.'.
In this simple crossword, every word must be filled either from left to right (horizontally) or from top to bottom (vertically).
A cell containing '#' is a blocked cell that is supposed to be ignored (i.e. not filled with any character).
A cell containing 'r' implies that there should be at least one word filled horizontally (from left to right) either starting at or ending at this position.
A cell containing 'c' implies that there should be at least one word filled vertically (from top to bottom) either starting at or ending at this position.
A cell containing 'b' implies that there should be at least one word filled vertically (from top to bottom) either starting at or ending at this position and another word filled horizontally (from left to right) either starting at or ending at this position.
There should not be more than one horizontally filled word in a row.
There should not be more than one vertically filled word in a column.
You are also given the list of words that solve the crossword puzzle, determine a way to write the given words in the grid following the above constraints. Every word that is given should be written in the crossword.
It is guaranteed that all words given have different lengths.
It is also guaranteed that for every word to be filled, the corresponding starting and ending positions are given in the grid as 'r', 'c' or 'b'.
In case there is no solution satisfying the given conditions print "Invalid" instead.
Input
First line contains 2 space separated integers n,m denoting the number of rows and columns of the grid.
Next n lines contain m characters each denoting the grid.
A '#' denotes that the cell is blocked, i.e. contains no characters
A '.' denotes an empty cell that should be filled with some character
An 'r' denotes that there exists a word that should be filled horizontally (i.e. from left to right) starting from this position
A 'c' denotes that there exists a word that should be filled vertically (i.e. from top to bottom) starting from this position
A 'b' denotes that there exists a word that is should be filled vertically (i.e. from top to bottom) starting from this position and another word that is to be filled horizantally (i.e. from left to right) starting from this position.
The next line contains a single integer w, the number of words to be filled
The next w lines each contains a string consisting of lower case english letters, a word that is to be written on the crossword.
Output
If there is no solution then print "Invalid", otherwise the solution will always be unique.
Print n lines each containing m characters denoting the value of the cell
A '#' cell should remain as is
Every '.', 'r', 'c' and 'b' cell given in the input should be replaced by an english character from 'a' to 'z' such that it satisfies the problem constraints
Constraints: 1≤n,m≤50
Every word in the dictionary has different length and contains at least 2 characters
There is always either a unique solution satisfying the given constraints or no solution.
Sample Input
8 8
b.c..r##
.#r.r###
.#rr####
.#c#####
.#######
.#######
.#######
c#######
5
solution
sample
many
ash
no
Sample Output
sample##
o#ash###
l#no####
u#y#####
t#######
i#######
o#######
n#######
Sample Input 2
8 8
b...c..r
.###r.r#
.###rr##
.###c###
.#######
c#######
########
########
5
this
sample
has
no
solution
Sample Output 2
Invalid
Explanation
The given words are filled into the crossword as shown for the first sample input.
We can fill the second sample as follows, observe that "no" cannot be filled in the remaining positions.
solution
a###has#
m###i.##
p###s###
l#######
e#######
########
########
Hence the answer is "Invalid".
What I have tried:
#include <stdio.h>
#include <string.h>
#define MAX_GRID 100
int num_rows, num_cols;
char grid[MAX_GRID][MAX_GRID];
char new_grid[MAX_GRID][MAX_GRID];
int num_words;
int len_words[MAX_GRID];
char words[MAX_GRID][MAX_GRID];
int find_row(int row, int col){
int len_word = 2;
int col_end;
for (col_end = col+1; grid[row][col_end] != 'r'; col_end++)
len_word++;
grid[row][col_end] = 'R';
int word;
for (word = 0; word < num_words; word++)
if (len_word == len_words[word])
break;
if (word == num_words)
return 0;
if (new_grid[row][col] != '.'){
if (new_grid[row][col] != words[word][0]){
return 0;
}
}
for (int i = 0; i < len_words[word]; i++)
new_grid[row][col+i] = words[word][i];
return 1;
}
int find_col(int row, int col){
int len_word = 2;
int row_end;
for (row_end = row+1; grid[row_end][col] != 'c'; row_end++)
len_word++;
grid[row_end][col] = 'C';
int word;
for (word = 0; word < num_words; word++)
if (len_word == len_words[word])
break;
if (word == num_words)
return 0;
if (new_grid[row][col] != '.'){
if (new_grid[row][col] != words[word][0]){
return 0;
}
}
for (int i = 0; i < len_words[word]; i++)
new_grid[row+i][col] = words[word][i];
return 1;
}
int main(){
scanf("%d %d", &num_rows, &num_cols);
for (int i = 0; i < num_rows; i++)
scanf("%s", grid[i]);
for (int i = 0; i < num_rows; i++)
for (int j = 0; j < num_cols; j++)
new_grid[i][j] = '.';
scanf("%d", &num_words);
for (int i = 0; i < num_words; i++)
{
scanf("%s", words[i]);
len_words[i] = strlen(words[i]);
}
int is_valid = 1;
for (int row = 0; row < num_rows; row++){
for (int col = 0; col < num_cols; col++){
if (grid[row][col] == '.'){
continue;
}
else if (grid[row][col] == '#'){
new_grid[row][col] = '#';
}
else if (grid[row][col] == 'b'){
if (find_row(row, col) == 0)
is_valid = 0;
if (find_col(row, col) == 0)
is_valid = 0;
}
else if (grid[row][col] == 'r'){
if (find_row(row, col) == 0)
is_valid = 0;
}
else if (grid[row][col] == 'c'){
if (find_col(row, col) == 0)
is_valid = 0;
}
}
}
if (is_valid == 0)
printf("Invalid\n");
else if(is_valid == 1){
for (int i = 0; i < num_rows; i++){
for (int j = 0; j < num_cols; j++)
printf("%c", new_grid[i][j]);
printf("\n");
}
}
return 0;
}
It runs correctly on the test cases, but when i submit it, it shows runtime error.