Pagini recente » Cod sursa (job #1608884) | Cod sursa (job #549152) | Cod sursa (job #868512) | Cod sursa (job #1942018) | Cod sursa (job #2119217)
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
vector <pair<int, int> > dame;
int n; //int board[1001][1001];
ifstream f("dame.in");
ofstream g("dame.out");
void afisare(int board[1001][1001])
{
g << n << endl; int i,j;
for(i=0;i<dame.size();i++)
{
g << dame[i].first << " " << dame[i].second << endl;
}
/* for (i=0;i<n;i++)
{
for (j=0;j<n;j++)
{
g << board[i][j] << " ";
}
g << endl;
}*/
}
int pairs(int board[1001][1001])
{
int i,j;
for (i=0;i<n;i++)
{
for (j=0;j<n;j++)
{
if (board[i][j]==1)
{
dame.push_back(make_pair(i,j));
}
}
}
afisare(board);
}
int checkIfSafe(int board[1001][1001],int i,int j)
{
int it; int ii,ij;
//cout << "s";
for (it=i;it>=0;it--)
{
if (board[it][j]==1)
{
return false;
}
}
ii=i;
ij=j;
//cout << "s";
while(ii>=0 && ij>=0)
{
if (board[ii][ij]==1)
{
return false;
}
ii--;
ij--;
}
ii=i;
ij=j;
while(ii>=0 && ij<=n)
{
if (board[ii][ij]==1)
{
return false;
}
ii--;
ij++;
}
return true;
}
int solveNQ(int board[1001][1001], int i)
{
//cout << "s";
if (i==n)
{
return true;
}
//[i][j];
// checkIfSafe();
int j;
// cout << "s";
for (j=0;j<n;j++)
{
if (checkIfSafe(board,i,j))
{
board[i][j]=1;
//solveNQ(board,i+1);
if ( solveNQ(board, i+1) )
// cout << "h";
return true;
board[i][j]=0;
}
}
return false;
}
int board[1001][1001];
int main()
{
f >> n;
// int board[1001][1001];
int i,j;
//cout << "s";
for (i=0;i<n;i++)
{
for (j=0;j<n;j++)
{
board[i][j]=0;
}
}
solveNQ(board,0);
pairs(board);
// cout << board[0][2];
return 0;
}