11585 - Nurikabe

[Chirag Chheda]

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??

waiting for ur reply

[vahid sanei]

after check all of numbers ,nurikabe shouldn`t have dot, and for each number that should have exactly n dots
( where n is number)

[Chirag Chheda]

I am still not able to get an Acc for this problem. Can someone plz help me by posting some test i/o.
Thnx

[sujon]

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>
#define shaded  100000000
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)
			if( g[i][j]==shaded&&!visit[i][j])
				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)
			if( g[i][j]!=shaded&&!visit[i][j])
				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)
			if( g[i][j]!=shaded&&!visit[i][j])
				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]=='#')
					g[i][j]=shaded;		
		}


		////////// checking shaded region /////////
	
		int check=0;
		for(i=0;i<m&&!check;i++)
			for(j=0;j<n;j++)
				if(g[i][j]==shaded)
				{
					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++)
				if(g[i][j]==shaded&&!visit[i][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++)
				  if(g[i][j]&&g[i][j]<shaded&&!visit[i][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));

				 if(g[i][j]!=shaded&&!visit[i][j])
				 {
					 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++)
					  if(g[i][j]==shaded&&g[i+1][j]==shaded&&g[i][j+1]==shaded&&g[i+1][j+1]==shaded)
					  {
						  valid=0;
						  break;
					  
					  }

					  sujon=0;

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

		printf("solved\n");

			  
	}
	




return 0;
}

[/code]

[Vytenis]

One tricky case is when there is a number in a shaded cell. In such case "non solved" must be printed.

[dibery]

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