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

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


2D НИМ
http://acm.pku.edu.cn/JudgeOnline/problem?id=1021

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

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

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

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

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

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

#include < iostream >
#include < vector >
using namespace std;

vector< vector<int> > s1,s2;

void print(int a[100][100]);
void find(int a[100][100],int num);
void gene(int a[100][100]);
vector<int> sortt(vector<int> s);
vector< vector<int> > get(int a[100][100]);
int t,w,h,n,x,y,countt;
int main()
{
cin>>t;
for(int i=0;i<t;i++)
{
int a[100][100]={0};
int b[100][100]={0};

cin>>w>>h>>n;
for(int j=0;j<n;j++){cin>>x>>y;a[y][x]=1;}
for(int j=0;j<n;j++){cin>>x>>y;b[y][x]=1;}

gene(a);
vector< vector<int> > ss1=get(a);
gene(b);
vector< vector<int> > ss2=get(b);

for(int j=0;j<ss1.size();j++)ss1[j]=sortt(ss1[j]);
for(int j=0;j<ss2.size();j++)ss2[j]=sortt(ss2[j]);

if(ss1.size()==ss2.size())
{
vector<int> flag(ss1.size(),0);
for(int j=0;j<ss1.size();j++)
{
for(int k=0;k<ss2.size();k++)
{
if(flag[k]!=1&&ss1[j].size()==ss2[k].size())
{
int l;
for(l=0;l<ss1[j].size();l++)
{
if(ss1[j][l]!=ss2[k][l])break;
}
if(l==ss1[j].size())
{
flag[k]=1;
}
}
}
}
int m;
for(m=0;m<flag.size();m++)
{
if(flag[m]!=1)break;
}
if(m!=flag.size())
{
cout<<"NO"<<endl;
}
else
{
cout<<"YES"<<endl;
}
}
else
{
cout<<"NO"<<endl;
}
}

return 0;
}

vector< vector<int> > get(int a[100][100])
{
vector<int> temp;
vector< vector<int> > ss(countt-1,temp);
for(int i=0;i<h;i++)
{
for(int j=0;j<w;j++)
{
if(a[i][j]!=0)
{
int noof=0;
int xs[8]={i-1,i-1,i-1,i,i,i+1,i+1,i+1};
int ys[8]={j-1,j,j+1,j-1,j+1,j-1,j,j+1};
for(int k=0;k<8;k++)
{
if(xs[k]>-1&&xs[k]<h&&ys[k]>-1&&ys[k]<w)
{
if(a[xs[k]][ys[k]]==a[i][j])
{
noof++;
}
}
}
ss[a[i][j]-2].push_back(noof);
}
}
}
return ss;
}

void gene(int a[100][100])
{
find(a,1);

countt=1;
while(x!=-1&&y!=-1)
{
vector<int> xx(1,x),yy(1,y);
a[x][y]=countt+1;
while(xx.size()!=0)
{
vector<int> tmpx,tmpy;
for(int i=0;i<xx.size();i++)
{
int xs[4]={xx[i]-1,xx[i],xx[i],xx[i]+1};
int ys[4]={yy[i],yy[i]-1,yy[i]+1,yy[i]};
for(int k=0;k<4;k++)
{
if(xs[k]>-1&&xs[k]<h&&ys[k]>-1&&ys[k]<w)
{
if(a[xs[k]][ys[k]]==1)
{
a[xs[k]][ys[k]]=countt+1;
tmpx.push_back(xs[k]);
tmpy.push_back(ys[k]);
}
}
}
}
xx=tmpx;
yy=tmpy;
}

countt++;
find(a,1);
}
}

vector<int> sortt(vector<int> s)
{
for(int i=0;i<s.size()-1;i++)
{
for(int j=0;j<s.size()-1;j++)
{
if(s[j]>s[j+1])
{
s[j]=s[j]+s[j+1];
s[j+1]=s[j]-s[j+1];
s[j]=s[j]-s[j+1];
}
}
}
return s;
}

void find(int a[100][100],int num)
{
x=-1;y=-1;
for(int i=0;i<h;i++)
{
for(int j=0;j<w;j++)
{
if(a[i][j]==num)
{
x=i;
y=j;
return;
}
}
}
}

void print(int a[100][100])
{
cout<<endl;
for(int i=0;i<h;i++)
{
for(int j=0;j<w;j++)
{
cout<<a[i][j];
}cout<<endl;
}cout<<endl;
}
Попередня Зміст Наступна
В системі: гості - (1); користувачі - (0)