My slow solution to live archive problem #3476

light.cpp

using namespace std;
#include <algorithm>
#include <iostream>
#include <iterator>
#include <numeric>
#include <sstream>
#include <fstream>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>

#define foreach(x, v) for (typeof (v).begin() x=(v).begin(); x !=(v).end(); ++x)
#define For(i, a, b) for (int i=(a); i<(b); ++i)
#define D(x) cout << #x " is " << x << endl

const int MAXN = 10;

int n, m;
int board[MAXN][MAXN];
int lit[MAXN][MAXN];
bool lamp[MAXN][MAXN];


void print_board(){
    for (int i = 0; i < n; ++i){
        for (int j = 0; j < m; ++j){
            printf("%3d ", !lamp[i][j] ? (!lit[i][j] ? board[i][j] : 100) : 111);
        }
        printf("\n");
    }
    printf("\n");
}

bool finished(){
    for (int i = 0; i < n; ++i){
        for (int j = 0; j < m; ++j){
            if (board[i][j] == -2 and !lit[i][j]) return false; //Not lit
            if (board[i][j] > 0) return false; //Not exactly that number of lamps
        }
    }
    return true;
}

bool space(int i, int j){
    if (i < 0 or i >= n or j < 0 or j >= m) return true;
    return board[i][j] != 0;
}

bool can_put(int i, int j){
    assert(board[i][j] == -2);
    return ( (lit[i][j] == 0) and space(i-1, j) and space(i+1, j) and space(i, j-1) and space(i, j+1));
}

void reduce(int i, int j){
    if (i < 0 or i >= n or j < 0 or j >= m) return;
    if (board[i][j] < 0) return;
    board[i][j]--;
    assert(board[i][j] >= 0);
}

void increase(int i, int j){
    if (i < 0 or i >= n or j < 0 or j >= m) return;
    if (board[i][j] < 0) return;
    board[i][j]++;
    assert(board[i][j] <= 4);
}

void put(int i, int j){
    reduce(i-1, j); reduce(i+1, j); reduce(i, j-1); reduce(i, j+1);
    
    for(int ii = i-1; ii >= 0 and board[ii][j] == -2; ii--) lit[ii][j]++;
    for(int ii = i+1; ii < n  and board[ii][j] == -2; ii++) lit[ii][j]++;
    for(int jj = j-1; jj >= 0 and board[i][jj] == -2; jj--) lit[i][jj]++;
    for(int jj = j+1; jj < m  and board[i][jj] == -2; jj++) lit[i][jj]++;
    
    lit[i][j]++;
    lamp[i][j] = true;
    assert(lit[i][j] == 1);

}

void remove(int i, int j){
    increase(i-1, j); increase(i+1, j); increase(i, j-1); increase(i, j+1);
    
    for(int ii = i-1; ii >= 0 and board[ii][j] == -2; ii--) lit[ii][j]--;
    for(int ii = i+1; ii < n  and board[ii][j] == -2; ii++) lit[ii][j]--;
    for(int jj = j-1; jj >= 0 and board[i][jj] == -2; jj--) lit[i][jj]--;
    for(int jj = j+1; jj < m  and board[i][jj] == -2; jj++) lit[i][jj]--;
    
    lit[i][j]--;
    lamp[i][j] = false;
    assert(lit[i][j] == 0);
}

bool can(int i, int j, int lamps){
    if (j == m){
        for (int ii = 0; ii < i; ++ii){
            for (int jj = 0; jj < m; ++jj){
                if (board[i][j] > 0) return false;
            }
        }
        return can(i+1, 0, lamps);
    }
    
    int cells_left = m * (n-i-1) + m - j;
    if (lamps > cells_left) return false;
    
    if (i == n or lamps == 0){
        // printf("Calling can(%d, %d, %d)\n", i, j, lamps);
        // if (lamps == 0) print_board();
        return finished();
    }
    
    assert(0 <= i and i < n and 0 <= j and j < m);
    

    
    if (board[i][j] != -2){
        if (board[i][j] > 2) return false;
        return can(i, j+1, lamps);
    }
    
    if (can_put(i, j)){
        put(i, j);    
        if (can(i, j+1, lamps-1)) return true;
        remove(i, j);
    }
    if (can(i, j+1, lamps)) return true;
    
    return false;
}



int main(){
    while (cin >> n >> m){
        if (n == 0 and m == 0) break;
        
        for (int i = 0; i < n; ++i){
            for (int j = 0; j < m; ++j){
                board[i][j] = -2;
                lit[i][j] = 0;
                lamp[i][j] = false;
            }
        }
        
        int b; cin >> b;
        int clear = n * m - b;
        while (b--){
            int i, j, k; 
            cin >> i >> j >> k;
            board[i-1][j-1] = k;
        }
        
        int lamps = 0;
        while (lamps <= clear){
            if (can(0, 0, lamps)) break;
            lamps++;
        }
        
        if (lamps <= clear) cout << lamps << endl;
        else puts("No solution");
    }
    return 0;
}