Talsu.net :: Programming Challenges - 작은 비숍(Little Bishops)

'재귀'에 해당되는 글 1건

2009/10/15 Programming Challenges - 작은 비숍(Little Bishops)

Study/Programming Challenges2009/10/15 00:46

Programming Challenges - 작은 비숍(Little Bishops)

문제 <- 클릭

이런 스타일의 문제에 약하다 생각 했는데 역시 힘들다.. 풀긴 했으나 시간 제한에 자꾸 걸린다 그것도 턱없이..

시험 몇일 남지도 않았는데 왠지 이런 스타일의 문제가 나올꺼 같아 불안 하다..
어쨋든 아직 미완..

#include <iostream>
#include <vector>
#include <deque>
//class FieldOld{
//	typedef std::pair<int, int> POS;
//	std::vector<POS> stack;
//	int fieldSize;
//public:
//	FieldOld(int size):fieldSize(size){}
//
//	int get(int x, int y){
//		if(x<0 || x > (fieldSize-1) || y < 0 || y > (fieldSize - 1))
//			return -1;
//		POS pos(x,y);
//		std::vector<POS>::iterator it;
//		for(it = stack.begin(); it!= stack.end(); ++it){
//			if((*it) == pos)
//				return 1;
//		}
//		return 0;
//	}
//	void push(int x, int y){
//		POS pos(x,y);
//		stack.push_back(pos);
//	}
//	void pop(){
//		if(!stack.empty())
//			stack.pop_back();
//	}
//
//	int size(){
//		return fieldSize;
//	}
//
//	int stackSize(){
//		return stack.size();
//	}
//
//
//};

class Field{
	typedef std::pair<int, int> POS;
	std::deque<POS> stack;

//std::vector< std::vector<int> > field;
	char field[8][8];
	int fieldSize;
public:
	Field(int size):fieldSize(size){
		//field.resize(size);
		//std::vector< std::vector<int> >::iterator it;
		//for(it = field.begin(); it!=field.end(); ++it){
		//	it->resize(size);
		//	std::vector<int>::iterator iit;
		//	for(iit = it->begin(); iit!= it->end(); ++iit){
		//		*iit = 0;
		//	}
		//}
		for(int i = 0 ; i < 8; ++i){
			for(int j = 0; j < 8; ++j){
				field[i][j] = 0;
			}
		}

}

int get(int x, int y){
		if(x<0 || x > (fieldSize-1) || y < 0 || y > (fieldSize - 1))
			return -1;
		//POS pos(x,y);
		//std::vector<POS>::iterator it;
		//for(it = stack.begin(); it!= stack.end(); ++it){
		//	if((*it) == pos)
		//		return 1;
		//}
		if(field[x][y] == 1)
			return 1;
		return 0;
	}
	void push(int x, int y){
		POS pos(x,y);
		stack.push_back(pos);
		field[x][y]=1;
//		attack(x,y,-1);
	}
	void pop(){
		if(!stack.empty()){
			/*POS pos(*(stack.end()));*/
			//field[pos.first][pos.second] = 0;
			POS pos = *(stack.rbegin());
			field[pos.first][pos.second] = 0;
//			attack(pos.first,pos.second,1);

stack.pop_back();
		}
	}

int size(){
		return fieldSize;
	}

int stackSize(){
		return stack.size();
	}

//void attackField(int x, int y, int damage){
	//	field[x][y]+=damage;
	//}

//int attackDirection(int x, int y, int xx, int yy, int damage) {  
	//	int value = get(x + xx, y + yy);
	//	if (value == -1)  
	//		return 0;  
	//	if (value == 0 || value == -2){
	//		attackField(x+xx, y+yy, damage);
	//		return attackDirection(x + xx, y + yy, xx, yy, damage);  
	//	}
	//	return 1;
	//}

//void attack(int x, int y, int damage){
	//	attackDirection(x,y,1,1,damage);
	//	attackDirection(x,y,1,-1,damage);
	//	attackDirection(x,y,-1,1,damage);
	//	attackDirection(x,y,-1,-1,damage);

//}

};

class LittleBishops{

int numberOfBishops;
	unsigned long long counter;
	Field field;

int checkDirection(int x, int y, int xx, int yy) {  
		int value = field.get(x + xx, y + yy);
		if (value == -1)  
			return 0;  
		if (value == 0 ) {
			return checkDirection(x + xx, y + yy, xx, yy);  
		}
		return 1;
	}

bool isAttack(int x, int y){
		//for (int i = -1; i <= 0; i++) {  
		//	for (int j = -1; j <= 1; j++) {  
		//		if (i != 0 && j != 0)  
		//			if (checkDirection(x, y, i, j) == 1)  
		//				return true;  
		//	}  
		//}

if (checkDirection(x, y, -1, 1) == 1)  
						return true;  
			if (checkDirection(x, y, -1, -1) == 1)  
						return true;  
		
		return false;
	}

void print(){
		for(int x = 0; x < field.size(); ++x){
			for( int y = 0; y < field.size(); ++y){
				std::cout<<field.get(x,y)<<" ";
			}
			std::cout<<std::endl;
		}
		std::cout<<std::endl;
	}

public:
	LittleBishops(int fieldSize, int numberOfBishops)
		:field(fieldSize),
		numberOfBishops(numberOfBishops),
		counter(0)
	{

}

int run(int startX, int startY){
		
		if(field.stackSize() == numberOfBishops){
			counter++;
			//print();
			field.pop();
			return 0;
		}
		for(int x = startX; x < field.size(); ++x){
			if(x != startX)
				startY = 0;
			for( int y = startY; y < field.size(); ++y){
				
				if(field.get(x,y) == 0 && !isAttack(x,y)){
					field.push(x,y);
					run(x,y);

}

}
		}
		field.pop();

return 1;
	}

unsigned long long getCount(){
		return counter;
	}

};

int main(){
	int size, number;
	while(true){
		std::cin>>size;
		std::cin>>number;
		if(size == 0 && number == 0)
			break;
		LittleBishops lb(size,number);
		//		lb.run();
		lb.run(0,0);
		std::cout<<lb.getCount()<<std::endl;
	}

return 0;
}

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-동일조건변경허락 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.

'Study > Programming Challenges' 카테고리의 다른 글

Programming Challenges - 작은 비숍(Little Bishops) (0)	2009/10/15
Programming Challenges - 동맹 휴업 (Hartal) (1)	2009/10/12
Programming Challenges - 포커 패 (Poker Hands) (0)	2009/10/12
Programming Challenges - 유쾌한 점퍼(Jolly Jumpers) (0)	2009/10/11
Programming Challenges - 호주식 투표법(Australian Voting) (0)	2009/10/08
Programming Challenges - 체크 확인 (Check the Check) (1)	2009/10/05

Posted by 탈수

TAG Algorithm, Little Bishops, Programming Challenges, 알고리즘, 작은 비숍, 재귀

Trackback 0 Comment 0

«이전 1 다음»

일	월	화	수	목	금	토
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30	31

태터데스크 관리자

태터데스크 메시지

Talsu.net

'재귀'에 해당되는 글 1건

Programming Challenges - 작은 비숍(Little Bishops)

'Study > Programming Challenges' 카테고리의 다른 글

TRACKBACK http://talsu.net/trackback/128

카테고리

공지사항

태그목록

최근에 올라온 글

최근에 달린 댓글

최근에 받은 트랙백

글 보관함

달력

링크