ソースコード
#include <stdio.h>
#include <time.h>
int scN, scM;
int scB[2][10];
clock_t scStartTime, scEndTime;
void scInput()
{
int i;
scanf("%d%d", &scN, &scM);
for (i = 0; i < scM; ++i)
{
scanf("%d%d", &scB[0][i], &scB[1][i]);
}
scStartTime = clock();
}
void scOutput(int s)
{
scEndTime = clock();
printf("Ans= %d, time=%d\n", s, (int)(scEndTime - scStartTime));
}
#include <cmath>
int check(int direct[])
{
int x = 20, y = 20;
int map[40] = {};
map[20] |= 1 << 20;
for (int i = 0; i < scM; i++)
map[20 + scB[0][i]] |= 1 << (20 + scB[1][i]);
for (int i = 0; i < scN - 1; i++)
{
switch (direct[i])
{
case 0:
x++;
break;
case 1:
y++;
break;
case 2:
x--;
break;
case 3:
y--;
break;
}
if (((map[x] >> y) & 1) == 1 || std::abs(x - 20) + std::abs(y - 20) > scN - i - 1)
return i;
map[x] |= 1 << y;
}
if (std::abs(x - 20) + std::abs(y - 20) == 1)
return scN - 1;
return scN - 2;
}
int move_up(int direct[], int start)
{
direct[start]++;
if (start > 0 && std::abs(direct[start] - direct[start - 1]) == 2)
direct[start]++;
for (int i = start; i > 0; i--)
{
if (direct[i] < 4)
break;
direct[i] = 0;
direct[i - 1]++;
if (i > 1 && std::abs(direct[i - 1] - direct[i - 2]) == 2)
direct[i - 1]++;
}
for (int i = start + 1; i < scN; i++)
direct[i] = 0;
return 0;
}
int solve()
{
int ans = 0;
int direct[20] = {};
int t = 0;
for (int i = 0; i < scM; i++)
{
if (std::abs(scB[0][i]) + std::abs(+scB[1][i]) < scN / 2)
{
if (i != t)
{
scB[0][t] = scB[0][i];
scB[1][t] = scB[1][i];
}
t++;
}
}
scM = t;
while (direct[0] < 4)
{
int status = check(direct);
if (status == scN - 1)
{
ans++;
move_up(direct, scN - 2);
}
else
move_up(direct, status);
}
return ans;
}
int main()
{
scInput();
scOutput(solve());
return 0;
}