比赛 |
20120919dfs |
评测结果 |
AAAAA |
题目名称 |
画海岛地图 |
最终得分 |
100 |
用户昵称 |
苏轼 |
运行时间 |
0.029 s |
代码语言 |
C++ |
内存使用 |
3.16 MiB |
提交时间 |
2012-09-19 20:24:52 |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
int n,hh[9][9],ll[9][9],answer=0,num[9]={0},ff[9][100][9]={0},nnum[9]={0};
int q[9][9],biao=0,w[9]={0},llnum[9]={0};
void ddfs(int x,int y);
void dfs(int x);
int main()
{
freopen ("island.in","r",stdin);
freopen ("island.out","w",stdout);
cin>>n;
for (int i=0;i<n;i++)
{
biao=i;
for (int j=0;j<n;j++)
{
int a=0;
cin>>a;
if (a)
{
hh[i][j]=a;
num[i]++;
}
else
{
break;
}
}
ddfs(0,0);
for (int k=0;k<n;k++)
w[k]=0;
}
for (int i=0;i<n;i++)
{
for (int j=0;j<n;j++)
{
int a=0;
cin>>a;
if (a)
{
ll[i][j]=a;
llnum[i]++;
}
else
{
break;
}
}
}
dfs(0);
if (answer==0)
cout<<"no";
return 0;
}
void dfs(int x)
{
if (x==n)
{
int aa=0,bb=0,tt=0;
/*for (int i=0;i<8;i++)
for (int j=0;j<8;j++)
{
if (i%2==0)
q[i][j]=(1-j%2);
else
q[i][j]=(j%2);
}
*/
for (int i=0;i<n;i++)
{
if (tt)
break;
for (int j=0;j<n;j++)
{
if (q[j][i]==1)
{
aa++;
}
else
{
if ((aa!=0&&aa!=ll[i][bb])||bb>llnum[i])
{
tt=1;
break;
}
if (aa!=0&&aa==ll[i][bb])
bb++;
aa=0;
}
}
if ((aa!=0&&aa!=ll[i][bb])||bb>llnum[i])
{
tt=1;
break;
}
aa=0;
bb=0;
}
if (tt)
return;
answer++;
cout<<answer<<endl;
for (int i=0;i<n;i++)
{
for (int j=0;j<n;j++)
{
if (q[i][j]==1)
{
cout<<'*';
}
else
{
cout<<' ';
}
}
cout<<endl;
}
}
else
{
for (int i=0;i<nnum[x];i++)
{
for (int j=0;j<n;j++)
{
q[x][j]=ff[x][i][j];
}
dfs(x+1);
}
}
}
void ddfs(int x,int y)
{
if (x==num[biao])
{
for (int i=0;i<n;i++)
{
ff[biao][nnum[biao]][i]=w[i];
}
nnum[biao]++;
}
else
{
for (int i=y;i<n;i++)
{
int tmp[9];
for (int r=0;r<n;r++)
{
tmp[r]=w[r];
}
int j;
j=hh[biao][x];
bool tt=0;
for (int k=i;k<i+j;k++)
{
w[k]=1;
if (k>n-1)
{
tt=1;
break;
}
}
if (tt)
continue;
ddfs(x+1,i+j+1);
for (int r=0;r<n;r++)
{
w[r]=tmp[r];
}
}
}
}