초보 자의 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;
}