| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 733 | 2013-03-01T13:01:02 Z | jyuno426 | 지도 색칠하기 (GA3_map) | C++ | 0 ms | 0 KB |
#include <algorithm>
int map[30][30];
int chk[30];
inline long long mapping(int num)
{
if(num <= 0) return 1;
if(map[num][0] == 0) return mapping(num-1);
bool color[5];
register int i;
long long ans = 0;
for(i=1;i<=4;i++) color[i] = false;
for(i=1;i<=map[num][0];i++)
{
if(map[num][i] <= num) break;
color[chk[map[num][i]]] = true;
}
else for(i=1;i<=4;i++)
{
if(!color[i])
{
chk[num] = i;
ans += mapping(num-1);
chk[num] = 0;
}
}
return ans;
}
bool cmp(int aa, int bb){return aa > bb;}
long long NumberOfMaps (int N, int M, int *A, int *B){
int i;
for(i=0;i<M;i++)
{
map[A[i]][++map[A[i]][0]] = B[i];
map[B[i]][++map[B[i]][0]] = A[i];
}
long long ans = 1;
for(i=1;i<=N;i++) std::sort(map[i]+1,map[i]+(map[i][0]+1),cmp);
for(i=1;i<=N;i++) if(map[i][0] == 0) ans *= 4;
while(map[N][0] == 0) N--;
chk[N] = 1;
if(N == 0) return ans;
return 4 * ans * mapping(N-1);
}