You have infinite SQUARE ceramic tiles(方形磁磚) of some sizes and you want to stick them to fill a rectangle area, which may have been partially covered. What will be the number of all the possible outcomes you can make to the empty space?
For example, if there is a 3-by-3 area that some regions have already been covered by some tiles as below:
| Empty | Empty | Covered |
| Empty | Empty | Empty |
| Covered | Empty | Empty |
and you have two kinds of tiles: 2-by-2 and 1-by-1, then there are 3 different outcomes you can make:(Let A* be the 2-by-2 tiles and B* be the 1-by-1 tiles)
| A1 | A1 | Covered |
| A1 | A1 | B1 |
| Covered | B2 | B3 |
| B1 | B2 | Covered |
| B3 | A1 | A1 |
| Covered | A1 | A1 |
| B1 | B2 | Covered |
| B3 | B4 | B5 |
| Covered | B6 | B7 |
The first line provides two integers, M and N, which are larger than or equal to 1 and less than 8, indicating the rectangle area that will be filled.
The second line provides an integer, K, that is larger than 1 and less than 5, indicating the amount of types of tiles. There will be ONE integer in each of the following K lines, indicating the sizes of the side of given square tiles. The K numbers are all different.
The following M lines, which have N bits in each line to indicate the unit area is filled or not. 1 denotes that the unit area is already filled; 0 denotes that it is empty. Every bit is separated by a space.
Note: There will always be some empty spaces to be filled.
You should output the number of all the possible outcome that can be made. Note that reflection and rotation is NOT considered. That's why the output of the example is 3 instead of 2(the case that rotation does not count).
Note: It is absolutely fine if you don't follow this template.
#include"function.h"
int isDone(void){
for (int i = 0; i < M; i++){
for (int j = 0; j < N; j++){
if(area[i][j] == 0) return 0;
}
}
return 1;
}
int isStickable(int k, int y, int x){
if sticking tile k would be out of the broader then say no
for the area covered by this tile {
/*is this space previously filled?*/
if some area not empty say no
}
say yes
}
void stick(int k, int y, int x){
for the area covered by this tile {
fill the space
}
}
void remove(int k, int y, int x){
for the area covered by this tile {
empty the space
}
}
void getnext(int *nexty, int *nextx){
for (int i = 0; i < M; i++){
for (int j = 0; j < N; j++){
if(area[i][j] == 0){
*nexty = i;
*nextx = j;
return;
}
}
}
}
int count(int y, int x){
int ret = 0;
int nexty, nextx;
/*check the ending condition*/
if(isDone())
return 1;
for all kinds of tiles {
/*combine above functions here*/
}
return ret;
}
Note: If you don't like the prototype of function count(int y, int x) defined in the header file, you may implement your idea like this:
int my_better_idea(int arg1, int arg2, ...){
...
my_better_idea(arg3, arg4, ...);
...
return result;
}
int count(int y, int x){
...
return my_better_idea(a, b, ...);
}