Cod sursă (job #492155)

#include <fstream>
#include <algorithm>
#include <vector>
#define NMAX 25
using namespace std;

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

struct info
{
    int x1,y1,x2,y2;
};

bool mapp[NMAX][NMAX];
vector < pair <int,int> > coord(NMAX);
vector < info > result(NMAX);
int dx[] = {0,1,-1,0};
int dy[] = {1,0,0,-1};
bool OK = false;
int N, M, I;

void print()
{
    for(int i = 0; i < I - 1 ; i++)
        fout << result[i].x1 << " " << result[i].y1 << " " << result[i].x2 << " " << result[i].y2 << "\n";

}

bool cond(int x,int y, int dx,int dy)
{
    if(!(mapp[x][y] == 1 && mapp[x + dx][y + dy] == 0))
        return false;
    if(x > N || x < 1 || y > M || y < 1)
        return false;
    if(x + dx > N || x + dx < 1 || y + dy > M || y + dy < 1)
        return false;
    return true;
}

void BKT(int left)
{
    if(left == I - 1)
    {
        print();
        exit(0);
        //print();
        return;
    }
    for(int k = 0; k < I; k++)
    {
        int DX = coord[k].first;
        int DY = coord[k].second;
        if(!mapp[DX][DY])
            continue;
        result[left].x1 = DX;
        result[left].y1 = DY;
        mapp[DX][DY] = 0;
        for(int i = 0 ; i < 4; i++)
        {
            if(cond(DX + dx[i],DY + dy[i],dx[i],dy[i]))
            {
                result[left].x2 = DX + 2 * dx[i];
                result[left].y2 = DY + 2 * dy[i];
                mapp[DX + 2 * dx[i]][DY + 2 * dy[i]] = 1;
                mapp[DX + dx[i]][DY + dy[i]] = 0;
                pair <int,int> cpp = coord[k];
                coord[k] = make_pair(DX + 2 * dx[i],DY + 2 * dy[i]);
                BKT(left + 1);
                coord[k] = cpp;
                mapp[DX + 2 * dx[i]][DY + 2 * dy[i]] = 0;
                mapp[DX + dx[i]][DY + dy[i]] = 1;
            }
        }
        mapp[DX][DY] = 1;
    }
}

int main()
{
    int dx, dy;
    fin >> N >> M >> I;
    for(int i = 0 ; i < I ; i++)
    {
        fin >> dx >> dy;
        mapp[dx][dy] = 1;
        coord[i] = make_pair(dx,dy);
    }
    BKT(0);
    return 0;
}