TC MPR1 D1 550 (CantorDust)

The problem statement can be viewed:
http://www.topcoder.com/stat?c=problem_statement&pm=10418&rd=13935

This problem is pretty much exactly the same as the D2 1000. However, there is one additional case we need to handle - patterns which are empty. This is fairly simple to translate from our previous algorithm/implementation. We simply need to check if the pattern supplied is empty (i.e. no X's) and if so make a special case computation.

Now the question is, how do we extend our original algorithm to cover this case? Take note that if there were no X's in the fractal then the number of different occurrences of our blank pattern would be:

(size - row size of the pattern + 1) * (size - column size of the pattern + 1)

However there are X's which act as obstacles from reaching this upper bound. So we simply calculate the number of occurrences where our pattern does not fit into the fractal. This is rather simple, just calculate the number of occurrences in which our pattern does fit and subtract it from the total number of occurrences for the associated row/column.

The total number of occurrences for a row is: size - row size of the pattern + 1
The total number of occurrences for a column is: size - column size of the pattern + 1
The number of occurrences where the pattern doesn't fit (per row): (size - row size of the pattern + 1) - pattern does fit in the row
The number of occurrences where the pattern doesn't fit (per col): (size - column size of the pattern + 1) - pattern does fit in the column

Using the same multiplication principle, the total number of occurrences where the pattern doesn't fit in the 2D space is simply the product of the two. Lastly, we just need to exclude this many occurrences from our upper bound calculation to yield the answer:

Total number of occurrences of an empty pattern: ((size - row size of the pattern + 1) * (size - column size of the pattern + 1)) - ((size - row size of the pattern + 1) - pattern does fit in the row) * ((size - column size of the pattern + 1) - pattern does fit in the column)

The implementation is as follows:

class CantorDust {
public:
   int occurrencesNumber(vector <string>, int);
};

string tab[10];
int visited[10];

string build(int num) {
   if (num == 0) return "X";
   if (visited[num]) return tab[num];
   visited[num] = 1;
   return tab[num] = build(num-1) + string(pow(3.0,(double)num-1),'.') + build(num-1);
}

int CantorDust::occurrencesNumber(vector <string> pattern, int t) {
   int res = 0;
   string str = build(t);
   string emptyRow = string(pattern[0].size(),'.');
   string emptyCol = string(pattern.size(),'.');
   string rows = "";
   int size = pow(3.0,(double)t);
   for (int i = 0; i < pattern.size(); i++) {
      if (pattern[i] == emptyRow) continue;
      if (rows != "" && rows != pattern[i]) return 0;
      rows = pattern[i];
   }
   string cols = "";
   for (int i = 0; i < pattern[0].size(); i++) {
      string col;
      for (int j = 0; j < pattern.size(); j++) {
         col += pattern[j][i];
      }
      if (col == emptyCol) continue;
      if (cols != "" && cols != col) return 0;
      cols = col;
   } 
   bool isEmpty = false;
   if (cols == "" && rows == "") {
      cols = emptyCol;
      rows = emptyRow;
      isEmpty = true;
   }
   int numMatchRow = 0, numMatchCol = 0;
   string::size_type pos = 0;
   while ((pos = str.find(rows,pos)) != string::npos) {
      numMatchRow++;
      pos++;
   }
   pos = 0;
   while ((pos = str.find(cols,pos)) != string::npos) {
      numMatchCol++;   
      pos++;
   }
   if (isEmpty) {
      int exclude = (size - emptyRow.size() + 1 - 
         numMatchRow) * (size - emptyCol.size() + 1 - numMatchCol);
      return (size - emptyRow.size() + 1) * 
         (size - emptyCol.size() + 1) - exclude;
   }
   return res = numMatchRow * numMatchCol;
}