POJ 1069 The Bermuda Triangle
경사 좌표 계 를 잘 이용 하여 각 점 을 표시 해 야 하 며, 원 리 는 인터넷 에 모두 있다.
제목 연결...
자신 이 한가 하고 지루 한 코드 로 시간 을 누 르 는데 뜻밖에도 32ms 까지 눌 렀 다.
#include <iostream>
#include <algorithm>
using namespace std;
#define CHOICE_R 0
#define CHOICE_C 1
int side_len, triangle_num, triangle[15],
data_map[55][55][2]; //0 1
int col_num[55][2];
bool isOK, num_map[26];
bool cmp(const int &a, const int &b)
{
return a<b;
}
int DFS_ROW(int row, int col, int choice)
{
int i, j, lenth, k, s, last_lenth;
bool ok ;
switch (choice)
{
case CHOICE_R:
for (; col <= col_num[row][1]; col++)
{
if (data_map[row][col][0])
{
break;
}
}
if (col > col_num[row][1])
{
return DFS_ROW(row, col_num[row][0], CHOICE_C);
}
last_lenth = col;
for (i = 0; i< triangle_num; i++)
{
lenth = triangle[i];
if (row+lenth > 2*side_len || col+lenth-1 > col_num[row][1])
{
return 0;
}
for (k = last_lenth; k < col+lenth; k++)
{
if (!data_map[row][k][0]) //
{
return 0; //
}
}
last_lenth = k;
for (j = row; j< row+lenth; j++)
{
for (k = col; k < col+lenth-j+row; k++)
{
data_map[j][k][0] = 0;
if (k != col)
{
data_map[j][k][1] = 0;
}
}
}//
ok = 1;
for (j = col+lenth; j<= col_num[row][1]; j++)
{
if (data_map[row][j][0])
{
if (DFS_ROW(row, j, CHOICE_R))
{
return 1;
}
else
{
ok = 0;
}
break;
}
}
if (j > col_num[row][1])
{
if (!DFS_ROW(row, col_num[row][0], CHOICE_C))
ok = 0;
else
return 1;
}
//
if (!ok)
{
for (s = row; s< row+lenth; s++)
{
for (k = col; k < col+lenth-s+row; k++)
{
data_map[s][k][0] = 1;
if (k != col)
{
data_map[s][k][1] = 1;
}
}
}
}
}
break;
case CHOICE_C:
for (; col <= col_num[row][1]; col++)
{
if (data_map[row][col][1])
{
break;
}
}
if (col > col_num[row][1])
{
if (row == 2*side_len-1) //
return 1;
else
return DFS_ROW(row+1, col_num[row][0], CHOICE_R);
}
for (i = 0; i< triangle_num; i++)
{
lenth = triangle[i];
if (row+lenth > 2*side_len || col > col_num[row+lenth-1][1] || col-lenth+1 < col_num[row+lenth-1][0])
{
return 0;
}
for (j = row, k = col; j< row+lenth && k > col-lenth; j++, k--)
{
if (!data_map[j][col][1] || !data_map[j][k][1])
{
return 0;
}
}
for (j = row; j< row+lenth; j++)
{
for (k = col-j+row; k <= col ; k++)
{
data_map[j][k][1] = 0;
if (k != col)
{
data_map[j][k][0] = 0;
}
}
}//
ok = 1;
for (j = col+1; j<= col_num[row][1]; j++)
{
if (data_map[row][j][1])
{
if (DFS_ROW(row, j, CHOICE_C))
{
return 1;
}
else
{
ok = 0;
}
break;
}
}
if (j > col_num[row][1])
{
if (row == 2*side_len-1)
return 1;
if (!DFS_ROW(row+1, col_num[row+1][0], CHOICE_R))
ok = 0;
else
return 1;
}
//
if (!ok)
{
for (j = row; j< row+lenth; j++)
{
for (k = col-j+row; k <= col ; k++)
{
data_map[j][k][1] = 1;
if (k != col)
{
data_map[j][k][0] = 1;
}
}
}
}
}
break;
}
return 0;
}
inline void solve()
{
memset(data_map, 0, sizeof(data_map));
int i, j;
for (i = 0; i<= side_len; i++)
{
for (j = side_len - i; j <= side_len*2; j++)
{
data_map[i][j][0] = data_map[i][j][1] = 1;
if (j == side_len*2)
{
data_map[i][j][0] = 0;
}
}
col_num[i][0] = side_len - i;
col_num[i][1] = side_len*2;
}
for (i = side_len; i< 2*side_len; i++)
{
for (j = 0; j < 3*side_len-i; j++)
{
data_map[i][j][0] = data_map[i][j][1] = 1;
if ( j == 0 )
{
data_map[i][j][1] = 0;
}
}
col_num[i][0] = 0;
col_num[i][1] = 3*side_len-i-1;
}
data_map[side_len][2*side_len][1] = 0;
if (DFS_ROW(0, side_len, CHOICE_R))
{
isOK = 1;
}
}
int main()
{
int sum, i, j, k, tmp_triangle[15];
cin>>sum;
while (sum--)
{
cin>>side_len>>triangle_num;
isOK = 0;
k = 0;
memset(num_map, 0, sizeof(num_map));
for (i = 0; i< triangle_num; i++)
{
cin>>tmp_triangle[i];
if (side_len % tmp_triangle[i] == 0)
{
isOK = 1;
goto my_stop;
}
if (tmp_triangle[i] > side_len)
{
isOK = 0;
goto my_stop;
}
if (!num_map[tmp_triangle[i]])
{
triangle[k++] = tmp_triangle[i];
for (j = tmp_triangle[i]; j < 26; j += tmp_triangle[i])
{
num_map[j] = 1;
}
}
}
triangle_num = k;
sort(triangle, triangle+triangle_num, cmp);
solve();
my_stop:
if (isOK)
{
printf("YES
");
}
else
{
printf("NO
");
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.