Pagini recente » Cod sursa (job #307346) | Cod sursa (job #1240601) | Cod sursa (job #1205212) | Cod sursa (job #1675227) | Cod sursa (job #959473)
Cod sursa(job #959473)
#include <cstdio>
#include <cstring>
#include <cassert>
#include <vector>
using namespace std;
const int MAX_R = 1005;
const int MAX_C = 1005;
const int Mod = 666013;
int R, C, K, Solution;
char Map[MAX_R][MAX_C];
/*
const int MAX_CONF = 1 << 22;
class Matrix {
public:
int rows, columns;
vector<vector<int>> values;
Matrix() {}
Matrix(const int rows, const int columns) {
this->rows = rows;
this->columns = columns;
values = vector<vector<int>>(rows, vector<int>(columns, 0));
}
int Encode() const {
int conf = 0, bit = 0;
for (int r = 0; r < rows; ++r) {
for (int c = 0; c < columns; ++c) {
conf ^= (values[r][c] << bit);
++bit;
}
}
return conf;
}
static Matrix Decode(const int conf, const int rows, const int columns) {
Matrix matrix = Matrix(rows, columns);
int bit = 0;
for (int r = 0; r < rows; ++r) {
for (int c = 0; c < columns; ++c) {
matrix.values[r][c] = (conf >> bit) & 1;
++bit;
}
}
return matrix;
}
void Print(FILE *stream) const {
for (int r = 0; r < rows; ++r, fprintf(stream, "\n"))
for (int c = 0; c < columns; ++c)
fprintf(stream, "%d ", values[r][c]);
}
};
int DP[MAX_CONF], BruteSolution;
inline bool MakeMove(const int row, const int column, Matrix &table) {
if (row < 0 || table.rows <= row || column < 0 || table.columns <= column)
return false;
if (table.values[row][column] == 0)
return false;
for (int r = row; r < min(table.rows, row + K); ++r)
for (int c = column; c < min(table.columns, column + K); ++c)
table.values[r][c] ^= 1;
return true;
}
int ComputeDP(const int conf) {
if (DP[conf] != -1)
return DP[conf];
DP[conf] = 0;
Matrix table = Matrix::Decode(conf, R, C);
for (int r = 0; r < R; ++r) {
for (int c = 0; c < C; ++c) {
Matrix newTable = table;
if (MakeMove(r, c, newTable))
DP[conf] |= (1 ^ ComputeDP(newTable.Encode()));
}
}
return DP[conf];
}
inline bool Match(const int conf) {
Matrix table = Matrix::Decode(conf, R, C);
bool match = true;
for (int r = 0; r < R && match; ++r)
for (int c = 0; c < C && match; ++c)
if (table.values[r][c] != Map[r][c] - '0' && Map[r][c] != '?')
match = false;
return match;
}
void Brute() {
memset(DP, -1, sizeof(DP));
DP[0] = 0;
for (int conf = 0; conf < (1 << (R * C)); ++conf)
if (Match(conf))
BruteSolution = (BruteSolution + ComputeDP(conf)) % Mod;
}
*/
inline int Pow(int value, int power) {
int result = 1;
for (; power > 0; power >>= 1) {
if (power & 1)
result = (1LL * result * value) % Mod;
value = (1LL * value * value) % Mod;
}
return result;
}
void Solve() {
//Brute();
int questions = 0;
for (int r = 0; r < R; ++r)
for (int c = 0; c < C; ++c)
if (Map[r][c] == '?')
++questions;
Solution = Pow(2, questions - 1);
/*
if (Solution != BruteSolution)
fprintf(stderr, "bad\n");*/
}
void Read() {
assert(freopen("bmat.in", "r", stdin));
assert(scanf("%d %d %d", &R, &C, &K) == 3);
for (int r = 0; r < R; ++r)
for (int c = 0; c < C; ++c)
assert(scanf(" %c", &Map[r][c]) == 1);
}
void Print() {
assert(freopen("bmat.out", "w", stdout));
printf("%d\n", Solution);
}
int main() {
Read();
Solve();
Print();
return 0;
}