반응형
https://algospot.com/judge/problem/read/BOARDCOVER
algospot.com :: BOARDCOVER
게임판 덮기 문제 정보 문제 H*W 크기의 게임판이 있습니다. 게임판은 검은 칸과 흰 칸으로 구성된 격자 모양을 하고 있는데 이 중 모든 흰 칸을 3칸짜리 L자 모양의 블록으로 덮고 싶습니다. 이
algospot.com
예제 : not yet
평가 : not yet
평가 : not yet
#include <stdio.h>
#include <stdlib.h>
int calculate(int H, int W, char **map);
int isPossiblePosition(int index, char **map, int H, int W, int type);
int check(char **map, int H, int W);
void valueCopy(char **backBufferMap, char **map, int size);
int main()
{
int TestCase;
if (scanf("%d", &TestCase) <= 30)
while (TestCase--)
{
int i;
int H, W;
// make map
char **Map;
scanf("%d %d", &H, &W);
// dynamic alloc
Map = (char **)malloc(sizeof(char *) * H);
Map[0] = (char *)malloc(sizeof(char) * W * H);
for (i = 1; i < H; i++)
Map[i] = Map[i - 1] + W;
if (H < 1 || H > 20 || W < 1 || W > 20)
break; // input error
// get MapData
for (i = 0; i < H; i++)
{
char buffer[21];
scanf("%s", &buffer);
int j;
for (j = 0; j < W; j++)
Map[i][j] = buffer[j];
}
printf("%d\n", calculate(H, W, Map));
free(Map[0]);
free(Map);
}
return 0;
}
/* checkedMap[] value alg
* 0 // first
*-------
* 1 | 5 // orientation 1
* 2 | 6 // orientation 2
* 3 | 7 // orientation 3
* 4 | 8 // orientation 4
*-------
* 9 // end
*/
int calculate(int H, int W, char **map)
{
int i;
int checkedMap[40] = {
0,
};
int possibleCount = 0;
// mark the checkedMap set '4', map position is impposible
for (i = 0; i < W * H; i++)
if ((*map)[i] == '#')
checkedMap[i] = 9;
int gate = 1;
while (gate)
{
gate = 0;
for (i = 0; i < W * H; i++)
if (checkedMap[i] < 9)
{
if (isPossiblePosition(i, map, H, W, checkedMap[i]))
{ // succ
if (checkedMap[i] == 0)
{
(*map)[i] = '#';
(*map)[i - 1] = '#';
(*map)[i + W] = '#';
checkedMap[i] = 5;
}
else if (checkedMap[i] == 1)
{
(*map)[i] = '#';
(*map)[i - 1] = '#';
(*map)[i - W] = '#';
checkedMap[i] = 6;
}
else if (checkedMap[i] == 2)
{
(*map)[i] = '#';
(*map)[i + 1] = '#';
(*map)[i - W] = '#';
checkedMap[i] = 7;
}
else if (checkedMap[i] == 3)
{
(*map)[i] = '#';
(*map)[i + 1] = '#';
(*map)[i + W] = '#';
checkedMap[i] = 8;
}
else if (checkedMap[i] == 4)
{
checkedMap[i] = 9;
}
// checkedMap[i]++;
}
else // fail
{
if (checkedMap[i] == 5)
{
(*map)[i] = '.';
(*map)[i - 1] = '.';
(*map)[i + W] = '.';
checkedMap[i] = 1;
}
else if (checkedMap[i] == 6)
{
(*map)[i] = '.';
(*map)[i - 1] = '.';
(*map)[i - W] = '.';
checkedMap[i] = 2;
}
else if (checkedMap[i] == 7)
{
(*map)[i] = '.';
(*map)[i + 1] = '.';
(*map)[i - W] = '.';
checkedMap[i] = 3;
}
else if (checkedMap[i] == 8)
{
(*map)[i] = '.';
(*map)[i + 1] = '.';
(*map)[i + W] = '.';
checkedMap[i] = 4;
}
// else if (checkedMap[i] == 4){ checkedMap[i] = 9; }
else
checkedMap[i]++;
}
gate = 1;
if (check(map, H, W))
possibleCount++;
}
}
return possibleCount;
}
int isPossiblePosition(int index, char **map, int H, int W, int type)
{
int i, j;
char **backBufferMap;
int isNotPosible = 0;
// is imposible block CHAR
if (type == 0)
if (index - 1 > -1 || index + W < H * W)
{
if ((*map)[index] == '#' || (*map)[index - 1] == '#' || (*map)[index + W] == '#')
return 0;
}
else
return 0;
else if (type == 1)
if (index - W > -1)
{
if ((*map)[index] == '#' || (*map)[index - 1] == '#' || (*map)[index - W] == '#')
return 0;
}
else
return 0;
else if (type == 2)
if (index - W > -1 || index + 1 < H * W)
{
if ((*map)[index] == '#' || (*map)[index + 1] == '#' || (*map)[index - W] == '#')
return 0;
}
else
return 0;
else if (type == 3)
if (index + W < H * W)
{
if ((*map)[index] == '#' || (*map)[index + 1] == '#' || (*map)[index + W] == '#')
return 0;
}
else
return 0;
else if (type == 4)
return 0;
// dynamic alloc
backBufferMap = (char **)malloc(sizeof(char *) * H);
backBufferMap[0] = (char *)malloc(sizeof(char) * W * H);
for (i = 1; i < H; i++)
backBufferMap[i] = backBufferMap[i - 1] + W;
// copy of MapData to backBuffer
// we calculate only On the backBUffer
valueCopy(backBufferMap, map, sizeof(char) * H * W);
for (i = 0; i < H; i++)
for (j = 0; j < W; j++) // Test All of Case
{
// is possible CHAR and count 1
// and add Queue
if (backBufferMap[i][j] == '.')
{
int count = 0;
int currentCount = 0;
int *Queue = (int *)malloc(sizeof(int) * W * H);
Queue[count++] = i * W + j;
(*backBufferMap)[Queue[count - 1]] = '#';
while (currentCount < count)
{
int max_position = W * H;
int _position = Queue[currentCount++];
// left
if (_position - 1 > 0 && (*backBufferMap)[_position - 1] == '.')
{
Queue[count++] = _position - 1;
(*backBufferMap)[Queue[count - 1]] = '#';
}
// right
if (_position + 1 < max_position && (*backBufferMap)[_position + 1] == '.')
{
Queue[count++] = _position + 1;
(*backBufferMap)[Queue[count - 1]] = '#';
}
// up
if (_position - W > 0 && (*backBufferMap)[_position - W] == '.')
{
Queue[count++] = _position - W;
(*backBufferMap)[Queue[count - 1]] = '#';
}
// down
if (_position + W < max_position && (*backBufferMap)[_position + W] == '.')
{
Queue[count++] = _position + W;
(*backBufferMap)[Queue[count - 1]] = '#';
}
// if l, r, u, d's CHAR possible, we change CHAR to '#'(is used)
}
if (count % 3 != 0) // mod != 3 alert fail space
{
isNotPosible = 1;
break;
}
free(Queue);
}
}
free(backBufferMap[0]);
free(backBufferMap);
// reach here, we know [i][j] CHAR is Possible
if (isNotPosible)
return 0;
return 1;
}
int check(char **map, int H, int W)
{
int i;
for (i = 0; i < W * H; i++)
if ((*map)[i] == '.')
return 0;
return 1;
}
void valueCopy(char **backBufferMap, char **map, int size)
{
while (size--)
(*backBufferMap)[size - 1] = (*map)[size - 1];
}반응형