Отримання знань

дистанційна підтримка освіти школярів


Бермудский треугольник
http://acm.pku.edu.cn/JudgeOnline/problem?id=1069

   Входные данные

   Выходные данные

   Пример входных данных

   Пример выходных данных

   Анализ условия и обсуждение идеи решения

   Пример решения на C++:

#include "iostream" 
#include "string.h"
#include "stdlib.h"
using namespace std;
const int maxn=100;
int ed;
int n,h;
int num;
int size[11];
int dir[2*maxn+1][2*maxn+1],done[2*maxn+1][2*maxn+1];
short ok[maxn][maxn][11];
struct vy{
int left,right;
}verge[11];
int com(const void *a,const void *b)
{
return *(int *)a-*(int *)b;
}
void init()
{
memset(size,0,sizeof(size));
memset(dir,0,sizeof(dir));
memset(done,0,sizeof(done));
memset(verge,0,sizeof(verge));
ed=0;
cin >> n;
int t;
cin >> t;
num=0;
int i;
for (i=1; i <= t; i++)
{
int k;
cin >> k;
int j;
for(j=1; j <= num && size[j]!=k; j++);
if (j > num) {
num++;
size[num]=k;
}
}
size[0]=0;
qsort(size,num+1,sizeof(size[0]),com);
}
void printout()
{
if (ed) cout << "YES" << endl;
else cout << "NO" << endl;
}
void chose()
{
int i,j;
for (i=1; i <= h; i++)
{
for (j=verge[i].left+1; j <= verge[i].right; j++)
{
dir[i][j]=-dir[i][j-1];
done[i][j]=0;
}
done[i][verge[i].left]=0;
}
for (i=1; i <= h; i++)
{
for (j=verge[i].left; j <= verge[i].right; j++)
{
int k;
for (k=1; k <= num; k++)
{
if (dir[i][j]==1) {
ok[i][j][k]=1;
int x=j,y=j;
int lm;
for (lm=1; lm <= size[k]; lm++)
{
if (x < verge[i+lm-1].left || y > verge[i+lm-1].right || i+lm-1 > h)
{ok[i][j][k]=0;
break;}
x--;
y++;
}
}
if (dir[i][j]==-1){
ok[i][j][k]=1;
int x=j,y=j+size[k]*2-2;
int lm;
for (lm=1; lm <= size[k]; lm++)
{
if (x < verge[i+lm-1].left || y > verge[i+lm-1].right || i+lm-1 > h)
{ok[i][j][k]=0;break;}
x++;
y--;
}
}
}
}
}
}
void make_tri()
{
h=n;
int i,j;
for (i=1; i <= h; i++)
{
verge[i].left=maxn-i+1;
verge[i].right=maxn+i-1;
dir[i][verge[i].left]=1;
}
chose();
}
void make_lin()
{
h=n;
int i,j;
for (i=1; i <= h; i++)
{
verge[i].left=maxn-n-i+1;
verge[i].right=maxn+n-i;
dir[i][verge[i].left]=1;
}
chose();
}
void make_ti()
{
h=n;
int i,j;
for (i=1; i <= h; i++)
{
verge[i].left=maxn-n-i+1;
verge[i].right=maxn+n+i-1;
dir[i][verge[i].left]=1;
}
chose();
}
void make_liu()
{
h=2*n;
int i,j;
for (i=1; i <= n; i++)
{
verge[i].left=maxn-n-i+1;
verge[i].right=maxn+n+i-1;
dir[i][verge[i].left]=1;
}
for (i=n+1; i <= h; i++)
{
verge[i].left=verge[2*n-i+1].left;
verge[i].right=verge[2*n-i+1].right;
dir[i][verge[i].left]=-1;
}
chose();
}
void dfs(int x,int y)
{
if (ed) return;
if (y > verge[x].right) {
if (x >= h) {ed=1;return;}
dfs(x+1,verge[x+1].left);
return;
}
if (done[x][y]) {dfs(x,y+1);return;}
int k;
for (k=1; k <= num; k++)
{
if (!ok[x][y][k]) break;
if (ed) break;
int bi=size[k],bj=verge[x+size[k]-1].right+1;
if (dir[x][y]==1)
{
int i,j;
int able=1;
int l,r;
l=y;
r=y;
for (i=1; i <= size[k]; i++)
{
for (j=l; j <= r; j++)
{
if (done[i+x-1][j]) {
able=0;
bi=i;
bj=j;
break;
}
else done[i+x-1][j]=1;
}
if (!able) break;
l--;
r++;
}
if (able) dfs(x,y+1);
l=r=y;
for (i=1; i <= bi; i++)
{
for (j=l; j <= r; j++)
{
if (i==bi && j==bj) break;
done[x+i-1][j]=0;
}
l--;
r++;
}
}
else
{
int i,j;
int able=1;
int l=y,r=y+2*size[k]-2;
for (i=1; i <= size[k]; i++)
{
for (j=l; j <= r; j++)
{
if (done[i+x-1][j]) {
able=0;
bi=i;
bj=j;
break;
}
else done[i+x-1][j]=1;
}
if (!able) break;
l++;
r--;
}
if (able) dfs(x,y+1);
l=y;
r=y+2*size[k]-2;
for (i=1; i <= bi; i++)
{
for (j=l; j <= r; j++)
{
if (i==bi && j==bj) break;
done[i+x-1][j]=0;
}
l++;
r--;
}
}
}
}
void work()
{
ed=0;
if (!ed) {
make_tri();
dfs(1,verge[1].left);
}
if (!ed) {
make_lin();
dfs(1,verge[1].left);
}
if (!ed) {
make_ti();
dfs(1,verge[1].left);
}
if (!ed) {
make_liu();
dfs(1,verge[1].left);
}
}
int main()
{
int cases;
cin >> cases;
while (cases--)
{
init();
work();
printout();
}
return 0;
}

 

Попередня Зміст Наступна
В системі: гості - (1); користувачі - (0)