UVa 103 - Stacking Boxes

// UVa 103 - Stacking Boxes

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;

int n, d;

struct box {
	int a;
	int s[10];
};

bool operator <(const box & a, const box & b) {
	for (int j = 0; j < d; j++)
		if (a.s[j] != b.s[j])
			return a.s[j] < b.s[j];
	return true;
}

bool inside(const box & a, const box & b) {
	for (int j = 0; j < d; j++)
		if (a.s[j] >= b.s[j])
			return false;
	return true;
}

int main() {
	while (cin >> n >> d) {
		box b[30];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < d; j++)
				cin >> b[i].s[j];
			b[i].a = i + 1;
			sort(b[i].s, b[i].s + d);
		}
		sort(b, b + n);

		int T[30], R[30];
		int sol = 0;
		for (int i = 0; i < n; i++) {
			T[i] = 0;
			R[i] = -1;
			for (int j = 0; j < i; j++) {
				if (inside(b[j], b[i]) && T[j] > T[i]) {
					T[i] = T[j];
					R[i] = j;
				}
			}
			T[i]++;
			if (T[i] > T[sol])
				sol = i;
		}

		cout << T[sol] << endl;
		stack<int> s;
		while (sol != -1) {
			s.push(sol);
			sol = R[sol];
		}
		while (s.size() > 1) {
			cout << b[s.top()].a << " ";
			s.pop();
		}
		cout << b[s.top()].a << endl;
	}
}