초보 자의 ACM 길 (1) 북 대 MOOC 알고리즘 기초 노트첫째 주매 거

1776 단어 초보 알고리즘
첫째 주 매 거
1. 퍼 펙 트 큐 브 (순환 조건 최적화)
2. 생리 주기 (순환 스텝 최적화)
3. POJ 1013 동전
4. POJ 1222 소등 문제 (부분 분석) (바 이 너 리 매 거 진 이용)
예제 4 즉, 소등 문 제 는 반복 해서 배 워 볼 만하 다. 아래 에 본인 의 AC 코드 를 첨부 한다.
#include
#include
#include
using namespace std;
//       5  
int map[6];  //   
int ing[6];  //     
int ans[6];  //   

int getnum(int num, int n) // num ==      , n ==       
{
	return (num >> n) & 1;
}

void change(int &num, int n)
{
	num ^= (1 << n);
	return;	
} 

void setnum(int &num, int n, int in) // in ==       
{
	if(in)
		num |= (1 << n);
	else
		num &= ~(1 << n);
	return;
} 

void outans(int n)
{
	cout << "PUZZLE #" << n << endl;
	for(int i = 0; i < 5; i++)
		for(int j = 0; j < 6; j++)
		{
			cout << getnum(ans[i], j);
			if(j == 5)
				cout << endl;
			else
				cout << " ";
		}
	return;
}

int main()
{
	int n, temp;
	cin >> n;
	for(int puzzle = 1; puzzle <= n; puzzle++)
	{
		int i, j, k;
		//     
		for(i = 0; i < 5; i++)
			for(j = 0; j < 6; j++)
			{
				cin >> temp;
				setnum(map[i], j, temp);
			}
		
		for(i = 0; i < 64; i++)
		{
			int swit = i;
			memcpy(ing, map, sizeof(map));
			
			for(j = 0; j < 5; j++)
			{
				ans[j] = swit;
				for(k = 0; k < 6; k++)
				{
					if(getnum(swit, k))          //         
					{
						if(k > 0)
							change(ing[j], k - 1);
						if(k < 5)
							change(ing[j], k + 1);
						change(ing[j], k);
					}
				}
				if(j < 4)						//         
					ing[j + 1] ^= swit;
				swit = ing[j];
			}
				if(ing[4] == 0)               
				{
					outans(puzzle);
					break;
				}
		}
	}
		
	return 0; 
}

좋은 웹페이지 즐겨찾기