lines.cpp

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

int m[300][300];
int H, W;

int lines[300];
int lines_backmap[300];
int cols[300];
int cols_backmap[300];

void swap_lines(int* vals, int* vals_backmap, int a, int b) {
	int val_a = vals[a];
	int val_b = vals[b];
	swap(vals[a], vals[b]);
	swap(vals_backmap[val_a], vals_backmap[val_b]);
}

int sort_thing(int* vals, int* vals_backmap, int n) {
	int swaps = 0;
	for (int i = 0; i < n; ++i) {
		int target = vals_backmap[i];
		if (i != target) {
			swap_lines(vals, vals_backmap, i, target);
			++swaps;
		}
	}
	return swaps;
}

bool lsortable(int data_l) {
	int line_id = m[data_l][0] / W;

	lines[data_l] = line_id;
	lines_backmap[line_id] = data_l;

	if (line_id == 0) {
		for (int x = 0; x < W; ++x) {
			int col_id = m[data_l][x];
			cols[x] = col_id;
			cols_backmap[col_id] = x;
		}
	}

	int lb = line_id*W;
	int ub = lb+W;
	for (int x = 0; x < W; ++x) {
		if (m[data_l][x] < lb || m[data_l][x] >= ub) {
			return false;
		}
	}
	return true;
}

bool csortable(int c) {
	int mark = m[0][c] % W;
	for (int y = 1; y < H; ++y) {
		if (m[y][c] % W != mark) {
			return false;
		}
	}
	return true;
}

int main() {
	while (cin >> H >> W) {
		bool invalid = false;
		for (int y = 0; y < H; ++y) {
			for (int x = 0; x < W; ++x) {
				int a;
				cin >> a;
				m[y][x] = a - 1;
			}
			if (!lsortable(y)) {
				invalid = true;
			}
		}

		if (invalid) {
			cout << "*\n";
			continue;
		}

		for (int x = 0; x < W; ++x) {
			if (!csortable(x)) {
				invalid = true;
				break;
			}
		}

		if (invalid) {
			cout << "*\n";
			continue;
		}

		cout << (sort_thing(lines, lines_backmap, H) + sort_thing(cols, cols_backmap, W)) << '\n';
	}
	return 0;
}

Link pro problema: http://www.urionlinejudge.com.br/judge/problems/view/1473