Pagini recente » Cod sursa (job #1241956) | Cod sursa (job #1258849)
#include <iostream>
#include <fstream>
#include <map>
int a[550][550];
long long sum[550][550];
int n;
int l1, c1, l2, c2;
long long v[9];
inline long long get_sum(int i1, int i2, int j1, int j2) {
return sum[i2][j2] - sum[i1 - 1][j2] - sum[i2][j1 - 1] + sum[i1 - 1][j1 - 1];
}
bool operator== (const std::map<long long, int>& left,
const std::map<long long, int>& right) {
typename std::map<long long, int>::const_iterator itl = left.begin();
typename std::map<long long, int>::const_iterator itr = right.begin();
while (itl != left.end() && itl != right.end()) {
if (itl->second == 0) {
itl++;
continue;
}
if (itr->second == 0) {
itr++;
continue;
}
if (itl->first != itr->first || itl->second != itr->second) {
return false;
}
itl++;
itr++;
}
while (itl != left.end() && itl->second == 0) {
itl++;
}
while (itr != right.end() && itr->second == 0) {
itr++;
}
if (itl != left.end() || itr != right.end()) {
return false;
}
return true;
}
void solve() {
// Count vectors.
std::map<long long, int> cts;
for (int i = 0; i < 9; ++i) {
cts[v[i]]++;
}
// The backtracking.
for (l1 = 1; l1 <= n - 2; ++l1) {
for (c1 = 1; c1 <= n - 2; ++c1) {
int s1 = get_sum(1, l1, 1, c1);
if (cts.count(s1) && cts[s1]) {
cts[s1]--;
for (l2 = l1 + 1; l2 <= n - 1; ++l2) {
long long s2 = get_sum(l1 + 1, l2, 1, c1);
long long s3 = get_sum(l2 + 1, n, 1, c1);
if (cts.count(s2) && cts[s2]) {
cts[s2]--;
if (cts.count(s3) && cts[s3]) {
cts[s3]--;
for (c2 = c1 + 1; c2 <= n - 1; ++c2) {
std::map<long long, int> os;
os[get_sum(1, l1, c1 + 1, c2)]++;
os[get_sum(l1 + 1, l2, c1 + 1, c2)]++;
os[get_sum(l2 + 1, n, c1 + 1, c2)]++;
os[get_sum(1, l1, c2 + 1, n)]++;
os[get_sum(l1 + 1, l2, c2 + 1, n)]++;
os[get_sum(l2 + 1, n, c2 + 1, n)]++;
if (os == cts) {
return;
}
}
cts[s3]++;
}
cts[s2]++;
}
}
cts[s1]++;
}
}
}
}
int main()
{
std::ifstream in("zone.in");
std::ofstream out("zone.out");
in >> n;
for (int i = 0; i < 9; ++i) {
in >> v[i];
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
in >> a[i][j];
sum[i][j] = a[i][j] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
}
}
solve();
out << l1 << " " << l2 << " " << c1 << " " << c2 << std::endl;
in.close();
out.close();
return 0;
}