Pagini recente » Cod sursa (job #1749432) | Cod sursa (job #1410853) | Cod sursa (job #239868) | Cod sursa (job #828138) | Cod sursa (job #1258874)
#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 all_zeros(const std::map<long long, int>& m) {
for (typename std::map<long long, int>::const_iterator it = m.begin();
it != m.end(); ++it) {
if (it->second != 0) {
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 = sum[l1][c1];
if (cts.count(s1) && cts[s1]) {
cts[s1]--;
for (l2 = l1 + 1; l2 <= n - 1; ++l2) {
long long s2 = sum[l2][c1] - sum[l1][c1];
long long s3 = sum[n][c1] - sum[l2][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) {
long long s4 = get_sum(1, l1, c1 + 1, c2);
long long s5 = get_sum(l1 + 1, l2, c1 + 1, c2);
long long s6 = get_sum(l2 + 1, n, c1 + 1, c2);
long long s7 = get_sum(1, l1, c2 + 1, n);
long long s8 = get_sum(l1 + 1, l2, c2 + 1, n);
long long s9 = get_sum(l2 + 1, n, c2 + 1, n);
cts[s4]--;
cts[s5]--;
cts[s6]--;
cts[s7]--;
cts[s8]--;
cts[s9]--;
if (all_zeros(cts)) {
return;
}
cts[s4]++;
cts[s5]++;
cts[s6]++;
cts[s7]++;
cts[s8]++;
cts[s9]++;
}
cts[s3]++;
}
cts[s2]++;
}
}
cts[s1]++;
}
}
}
}
int main()
{
FILE* in = fopen("zone.in", "r");
std::ofstream out("zone.out");
fscanf(in, "%d", &n);
for (int i = 0; i < 9; ++i) {
fscanf(in, "%lld", &v[i]);
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
fscanf(in, "%d", &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;
fclose(in);
out.close();
return 0;
}