neoevoke » [usaco] 1.5 Checker Challenge

[usaco] 1.5 Checker Challenge - usaco

2009.08.08 23:14 neoevoke Edit

친절하게도 무려 힌트가 6개나 있는 문제이다.

각 세로줄마다 각 대각선마다 하나씩 밖에 못가기 때문에 검사하는 bool 배열을 만들어서 돌려주고
위아래 대칭이라는 점에 착안하여 절반만 돌려야 통과하는 문제이다.
7까지는 그냥 돌려주고 나머지는 절반만 돌려서 *2했다.

/*
ID: neoevok1
PROG: checker
LANG: C++
*/
#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

int n;

int r[15];
bool c[15];
bool d1[30]; // r+c
bool d2[30]; // r-c+n

long long cnt=0;

vector<vector<int> > ret;

void dfs(int y, int x)
{
	r[y]=x;
	if(y>=n)
	{
		if(cnt<3)
		{
			vector<int> ret2;
			for(int i=1;i<=n;i++) ret2.push_back(r[i]);
			ret.push_back(ret2);
		}
		cnt++;
		return;
	}
	c[x]=1;
	d1[x+y]=1;
	d2[y-x+n]=1;

for(int i=1;i<=n;i++)
		if(c[i]==0 && d1[y+1+i]==0 && d2[y+1-i+n]==0)
			dfs(y+1,i);

c[x]=0;
	d1[x+y]=0;
	d2[y-x+n]=0;
	
}

int main() {
    ofstream fout ("checker.out");
    ifstream fin ("checker.in");

fin >> n ;

for(int i=0;i<15;i++) c[i]=0;
	for(int i=0;i<30;i++) d1[i]=0;
	for(int i=0;i<30;i++) d2[i]=0;

if(n<8)
	for(int i=1;i<=n;i++)
		dfs(1,i);
	else
	{
		for(int i=1;i<=n/2;i++)
			dfs(1,i);
		cnt*=2;	
		if(n%2==1)
			dfs(1,n/2+1);	
	}

for(int i=0;i<(int)ret.size();i++)
	{
		fout << ret[i][0];
		for(int j=1;j<(int)ret[i].size();j++)
			fout << " " << ret[i][j];
		fout << endl;
	}
	fout << cnt << endl;

return 0;
}

[usaco] 2.1 The Castle [usaco] 1.5 Superprime Rib

Trackbacks 0

엮인글 주소: http://dw.yutar.net/329399/7dd/trackback

Comments 0

Leave Comments

neoevoke소셜계의 김성모

[usaco] 1.5 Checker Challenge - usaco

Trackbacks 0

Comments 0

Leave Comments

Category

Recent Post

Recent Comment

Recent Trackback

Tag