Cod sursa(job #959473)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 8 iunie 2013 13:09:07
Problema Nowhere-zero Scor 0
Compilator cpp Status done
Runda Infoarena Cup 2013 Marime 3.76 kb
#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;
}