UVA Solution 269 - Counting Patterns - Solution in C++ | Volume 2

UVA Solution 269 - Counting Patterns - Solution in C++ | Volume 2

UVA Online Judge Solution 269 - Counting Patterns | Volume 2
UVA Problem Link - 269 - Counting Patterns

Problem Name: 269 - Counting Patterns
Problem Number : UVA - 269 - Counting Patterns
Online Judge : UVA Online Judge Solution
Volume: 2
Solution Language : C plus plus

UVA Solution 269 - Counting Patterns Code in CPP:

#include <stdio.h> 
#include <string.h>
#include <algorithm>
#include <stdlib.h>
#include <set>
#include <assert.h>
using namespace std;
set<int> S;
int n, m, path[20], way[131072][20], ways;

bool cmp (int l[], int r[]) {
    for (int i = 0; i < n; i++)
        if (l[i] != r[i])
            return l[i] > r[i];
    return false;
}

void check (int a[]) {
    int b[32];

    for (int i = 0; i < n; i++)
        b[i] = b[i+n] = a[i];
    for (int i = 0; i < n; i++)
        if (b[i] == a[0] && cmp(b+i, a))
            return;

    for (int i = 0; i < 2 * n; i++)
        b[i] = -b[i];
    for (int i = 0; i < n; i++)
        if (b[i] == a[0] && cmp(b+i, a))
            return;

    for (int i = 0; i < n; i++)
        swap(b[i], b[2*n-i-1]);
    for (int i = 0;  i < n; i++)
        if (b[i] == a[0] && cmp(b+i, a))
            return;

    for (int i = 0; i < 2 * n; i++)
        b[i] = -b[i];
    for (int i = 0; i < n; i++)
        if (b[i] == a[0] && cmp(b+i, a))
            return;

    memcpy(way[ways++], a, sizeof(int) * n);
}
void dfs(int idx, int sum) {
 if (abs(sum) > abs((n - idx) * path[0]))
  return;
 if (idx == n) {
  if (sum == 0) 
   check(path);
  return;
 }
 if (idx == 0) {
  for (int i = 1; i <= m; i++) {
   path[idx] = i;
   dfs(idx+1, sum + i);
  }
 } else {
  for (int i = -abs(path[0]); i <= abs(path[0]); i++) {
   path[idx] = i;
   dfs(idx+1, sum + i);
  }
 }
}
int main() {
 int cases = 0;
 while (scanf("%d %d", &n, &m) == 2 && n) {
  ways = 1;
  dfs(0, 0);
  if (cases++) 
   puts("");
  printf("%d\n", ways);
  for (int i = 0; i < ways; i++) {
   printf("(%d", way[i][0]);
   for (int j = 1; j < n; j++)
       printf(",%d", way[i][j]);
   puts(")");
  }
 }
 return 0;
}