Cod sursă (job #334058)

#include <fstream>
#include <vector>
#include <algorithm>
#include <iostream>
#include <assert.h>

using namespace std;

const int NMAX = 21, IMAX = 16;

struct nemuritor{
    int ox, oy;
} nemurit[IMAX];

bool camp[NMAX][NMAX];

vector< pair<int, int> > raspuns;


int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

int n, m, k, elim;

ifstream fin("immortal.in");
ofstream fout("immortal.out");


bool ok(int x, int y, int dir){
    if(x >= 1 && x <= n && y >= 1 && y <= m)
        if(x + dx[dir] >= 1 && x + dx[dir] <= n && y + dy[dir] >= 1 && y + dy[dir] <= m)
            if(!camp[x + dx[dir]][y + dy[dir]] && camp[x][y])
                return 1;
    return 0;
}


void afis(){
    for(int i = 0; i < (int)raspuns.size() - 1; i += 2)
        fout << raspuns[i].first << " " << raspuns[i].second << " " << raspuns[i + 1].first << " " << raspuns[i + 1].second << " \n";
}

bool folosit[NMAX][NMAX];

bool operator<(nemuritor a, nemuritor b){
    if(a.ox < b.ox)
        return 1;
    if(a.ox == b.ox)
        return a.oy < b.oy;
    return 0;
}

bool lupta(){
    if(elim == k - 1)
        return 1;
    int cnt = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cnt += camp[i][j];
        //    cerr << camp[i][j] << " ";
        }
      //  cerr << "\n";
    }
    //cerr << endl;
    assert(cnt == k - elim);
    for(int i = 1; i <= k; i++){
        if(!folosit[nemurit[i].ox][nemurit[i].oy]){
            raspuns.push_back(make_pair(nemurit[i].ox, nemurit[i].oy));
            folosit[nemurit[i].ox][nemurit[i].oy] = 1;
            for(int d = 0; d < 4; d++){
                int nextx = nemurit[i].ox + dx[d], nexty = nemurit[i].oy + dy[d];
                if(ok(nextx, nexty, d)){
                    camp[nemurit[i].ox][nemurit[i].oy] = camp[nextx][nexty] = 0;
                    camp[nextx + dx[d]][nexty + dy[d]] = 1;
                    folosit[nextx][nexty] = 1;
                    int copyx = nemurit[i].ox, copyy = nemurit[i].oy;
                    nemurit[i].ox = nextx + dx[d];
                    nemurit[i].oy = nexty + dy[d];
                    elim++;
                    raspuns.push_back(make_pair(nemurit[i].ox, nemurit[i].oy));
                    if(lupta())
                        return 1;
                    raspuns.pop_back();
                    nemurit[i].ox = copyx;
                    nemurit[i].oy = copyy;
                    camp[nemurit[i].ox][nemurit[i].oy] = camp[nextx][nexty] = 1;
                    camp[nextx + dx[d]][nexty + dy[d]] = 0;
                    folosit[nextx][nexty] = 0;
                    elim--;
                }
            }
            folosit[nemurit[i].ox][nemurit[i].oy] = 0;
            raspuns.pop_back();
        }
    }
    return 0;
}


int main()
{
    fin >> n >> m >> k;
    for(int i = 1; i <= k; i++){
        fin >> nemurit[i].ox >> nemurit[i].oy;
        camp[nemurit[i].ox][nemurit[i].oy] = 1;
    }
    //freopen("error.txt", "w", stderr);
    sort(nemurit + 1, nemurit + k + 1);
    elim = 0;
    lupta();
    afis();
    return 0;
}