Page 2 of 2

### Re: 11585 - Nurikabe

Posted: Tue Mar 10, 2009 6:42 pm
Hi vahid,
Can u tell him how did u incorporate such a thing in ur code in which the number of dots given in the description is less then the actual dots present in the nurikabe??

### Re: 11585 - Nurikabe

Posted: Tue Mar 10, 2009 9:11 pm
after check all of numbers ,nurikabe shouldn`t have dot, and for each number that should have exactly n dots
( where n is number)

### Re: 11585 - Nurikabe

Posted: Wed Mar 11, 2009 2:42 pm
I am still not able to get an Acc for this problem. Can someone plz help me by posting some test i/o.
Thnx

### Re: 11585 - Nurikabe

Posted: Sat Jun 27, 2009 2:41 pm
1. dfs() find out 1st constraint.
2. dfsb() find out 2nd constraint.
3. dfs2() find out 3rd constraint
4. then i find out 2*2 square using two for loop

I m getting continues WA. anyone plzzzzzzzzzzzzzzz help me

Code: Select all

``````[code]

///// dfs algorithom

#include<iostream>
#include<string.h>
#include<stdio.h>
//#include<stdlib.h>
using namespace std;

//typedef __int64 longlong;
//typedef long long longlong;

int m,n,visit[110][110];
long int g[110][110];

int found,c,sum;

void init()
{

int i,j;

for(i=0;i<=110;i++)
for(j=0;j<=110;j++)
{
visit[i][j]=0;
g[i][j]=0;
}

int sujon=0;

}

void dfs(int x,int y)
{

visit[x][y]=1;
c++;

int i,j,p=0;

for(i=x-1;i<=x+1;i++)
for(j=y-1;j<=y+1;j++)
{
p++;
if(p%2)
continue;
if(i>=0&&i<m&&j>=0&&j<n)
dfs(i,j);
}

}

//// for checking spaces //////

void dfsb(int x,int y)
{

visit[x][y]=1;
c++;
sum+=g[x][y];

int i,j,p=0;

for(i=x-1;i<=x+1;i++)
for(j=y-1;j<=y+1;j++)
{
p++;
if(p%2)
continue;
if(i>=0&&i<m&&j>=0&&j<n)
dfsb(i,j);
}

}

void dfs2(int x,int y)
{

if(x==0||x==m-1||y==0||y==n-1)
found=1;

visit[x][y]=1;

int i,j;

for(i=x-1;i<=x+1;i++)
for(j=y-1;j<=y+1;j++)
if(i>=0&&i<m&&j>=0&&j<n)
dfs2(i,j);

}

int main()
{

int set,i,j,d,r1,c1,value;
char temp[100];

//	freopen("input.txt","r",stdin);
gets(temp);
sscanf(temp,"%d",&set);

while(set--)
{
gets(temp);///blank

init();

gets(temp);
sscanf(temp,"%d %d %d",&m,&n,&d);

for(i=0;i<d;i++)
{
gets(temp);
sscanf(temp,"%d %d %d",&r1,&c1,&value);
g[r1][c1]=value;

}

for(i=0;i<m;i++)
{
gets(temp);
for(j=0;j<n;j++)
if(temp[j]=='#')
}

int check=0;
for(i=0;i<m&&!check;i++)
for(j=0;j<n;j++)
{
dfs(i,j);
check=1;
break;
}

if(!check)
{
printf("not solved\n");
continue;

}

int valid=1;
for(i=0;i<m&&valid;i++)
for(j=0;j<n;j++)
{

valid=0;
break;
}

int sujon=0;

if(!valid)
{
printf("not solved\n");
continue;
}

/////////// checking blank space    /////////

valid=1;
int total;
for(i=0;i<m&&valid;i++)
for(j=0;j<n;j++)
{
total=g[i][j];
c=0;
sum=0;
dfsb(i,j);
if(total!=c||sum!=total)
{
valid=0;
break;

}

}

sujon=0;

if(!valid)
{
printf("not solved\n");
continue;
}

valid=1;

///////////// checking third condition /////////

//init();
//memset(visit,0,sizeof(visit));
for(i=0;i<m;i++)
for(j=0;j<n;j++)
visit[i][j]=0;

for(i=0;i<m&&valid;i++)
for(j=0;j<n;j++)
{
// memset(visit,0,sizeof(visit));

{
found=0;
dfs2(i,j);
if(!found)
{
valid=0;
break;

}
}

}

sujon=0;

if(!valid)
{
printf("not solved\n");
continue;
}

/////////// checking fourth condition  //////////

valid=1;
for(i=0;i<m-1&&valid;i++)
for(j=0;j<n-1;j++)
{
valid=0;
break;

}

sujon=0;

if(!valid)
{
printf("not solved\n");
continue;
}

printf("solved\n");

}

return 0;
}

``````
[/code]

### Re: 11585 - Nurikabe

Posted: Thu Apr 15, 2010 3:39 am
One tricky case is when there is a number in a shaded cell. In such case "non solved" must be printed.

### Re: 11585 - Nurikabe

Posted: Fri Feb 20, 2015 3:28 pm
Just some more cases.
Input

Code: Select all

``````2
3 3 1
2 2 9
...
...
...
3 3 3
1 1 1
2 2 1
0 0 1
.##
###
##.``````
Output

Code: Select all

``````solved
solved``````