11585 - Nurikabe

All about problems in Volume 115. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Igor9669
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

11585 - Nurikabe

Post by Igor9669 » Sun Feb 22, 2009 6:45 am

Please explain me why in second example the answer is "not solved"???

3#1#2
.###.
.#1##
####3
2.#..

SerailHydra
New poster
Posts: 20
Joined: Mon Oct 20, 2008 6:26 am

Re: 11585 - Nurikabe

Post by SerailHydra » Sun Feb 22, 2009 11:41 am

"For any unshaded space b, there is a sequence of unshaded spaces starting at b and ending at a space on the edge of the grid where consecutive spaces in this sequence share a side or a corner. "

Igor9669
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

Re: 11585 - Nurikabe

Post by Igor9669 » Tue Feb 24, 2009 6:43 pm

I understood, that I don't understand this statement :D !
Could you please show me in the figure above, where is a mistake...

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Re: 11585 - Nurikabe

Post by sohel » Wed Feb 25, 2009 8:12 am

Code: Select all

3#1#2
.###.
.#1##
####3
2.#..
Look at the cell with coordinates (2,2) - there is no way to reach the edges of the grid following only unshaded spaces.

User avatar
vahid sanei
Learning poster
Posts: 84
Joined: Fri Jan 09, 2009 4:37 pm
Location: IRAN

Re: 11585 - Nurikabe

Post by vahid sanei » Thu Mar 05, 2009 8:26 pm

Sohel you got Acc in 0.170 sec
i use bfs for this problem but i got acc in 0,540 , how can i reduce time of my code ? :-?



thanks in advance
Impossible says I`m possible

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Re: 11585 - Nurikabe

Post by sohel » Fri Mar 06, 2009 7:31 am

I used dfs().
May be bfs() codes has some overheads. Another reason could be the extensive use of STLs. STL codes are inherently slow!
The time difference isn't actually that significant to cause any worry :). A high constant factor could be the reason for the difference in time.
You can also speed up by using efficient methods for reading the input.

User avatar
vahid sanei
Learning poster
Posts: 84
Joined: Fri Jan 09, 2009 4:37 pm
Location: IRAN

Re: 11585 - Nurikabe

Post by vahid sanei » Fri Mar 06, 2009 9:39 am

what is faster than scanf and printf ? :-?
Impossible says I`m possible

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Re: 11585 - Nurikabe

Post by sohel » Fri Mar 06, 2009 11:13 am

fread()

Igor9669
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

Re: 11585 - Nurikabe

Post by Igor9669 » Fri Mar 06, 2009 3:09 pm

I used dfs, but still WA....

Please anybody give some tests!
I don't know where I have a mistake...

What will be the answer for that test:

3

1 2 0
##

1 1 0
.

1 1 0
#

User avatar
vahid sanei
Learning poster
Posts: 84
Joined: Fri Jan 09, 2009 4:37 pm
Location: IRAN

Re: 11585 - Nurikabe

Post by vahid sanei » Fri Mar 06, 2009 3:20 pm

Input

Code: Select all

4
1 2 0
##
1 1 0
.
1 1 0
#
1 2 1
0 0 1
.#
Output

Code: Select all

not solved
not solved
not solved
solved
Impossible says I`m possible

Igor9669
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

Re: 11585 - Nurikabe

Post by Igor9669 » Fri Mar 06, 2009 3:38 pm

Finally accepted!!!!!
But my ac prog gives such answer on my test:

Code: Select all

3

1 2 0
##

1 1 0
.

1 1 0
#

Code: Select all

solved
not solved
solved

User avatar
vahid sanei
Learning poster
Posts: 84
Joined: Fri Jan 09, 2009 4:37 pm
Location: IRAN

Re: 11585 - Nurikabe

Post by vahid sanei » Fri Mar 06, 2009 6:38 pm

in every 2 x 2 subsquare there is at least one unshaded space.
those arent 2 x 2 subsquare but i checked
Impossible says I`m possible

Chirag Chheda
Learning poster
Posts: 74
Joined: Sat Jun 21, 2008 12:24 pm
Location: India

Re: 11585 - Nurikabe

Post by Chirag Chheda » Tue Mar 10, 2009 12:43 pm

I am getting WA for this problem. I cant find my mistake. Can someone help me?? :oops:

Code: Select all

#include<iostream>

using namespace std;

int r,c,ans;
char arr[102][102],s[102];
bool cnt[102][102],fl;

void dfs1(int i,int j)
{
     cnt[i][j]=1;
     ans++;
     
     if(i-1>=0 && arr[i-1][j]=='#' && cnt[i-1][j]==0) dfs1(i-1,j);
     if(i+1<r && arr[i+1][j]=='#' && cnt[i+1][j]==0) dfs1(i+1,j);
     if(j-1>=0 && arr[i][j-1]=='#' && cnt[i][j-1]==0) dfs1(i,j-1);
     if(j+1<c && arr[i][j+1]=='#' && cnt[i][j+1]==0) dfs1(i,j+1);          
}

void dfs(int i,int j)
{
     cnt[i][j]=1;
     ans++;

     if(i-1>=0 && arr[i-1][j]=='.' && cnt[i-1][j]==0) dfs(i-1,j);
     if(i+1<r && arr[i+1][j]=='.' && cnt[i+1][j]==0) dfs(i+1,j);
     if(j-1>=0 && arr[i][j-1]=='.' && cnt[i][j-1]==0) dfs(i,j-1);
     if(j+1<c && arr[i][j+1]=='.' && cnt[i][j+1]==0) dfs(i,j+1); 
}

void dfs2(int i,int j)
{
     if(i==0 || j==0 || i+1==r || j+1==c)
     fl=1;
     
     cnt[i][j]=1;
     
     if(i-1>=0 && arr[i-1][j]=='.' && cnt[i-1][j]==0) dfs2(i-1,j);
     if(i+1<r && arr[i+1][j]=='.' && cnt[i+1][j]==0) dfs2(i+1,j);
     if(j-1>=0 && arr[i][j-1]=='.' && cnt[i][j-1]==0) dfs2(i,j-1);
     if(j+1<c && arr[i][j+1]=='.' && cnt[i][j+1]==0) dfs2(i,j+1);
     
     if(i-1>=0 && j-1>=0 && arr[i-1][j-1]=='.' && cnt[i-1][j-1]==0) dfs2(i-1,j-1);
     if(i+1<r && j-1>=0 && arr[i+1][j-1]=='.' && cnt[i+1][j-1]==0) dfs2(i+1,j-1);
     if(i+1<r && j+1<c && arr[i+1][j+1]=='.' && cnt[i+1][j+1]==0) dfs2(i+1,j+1);
     if(i-1>=0 && j+1<c && arr[i-1][j+1]=='.' && cnt[i-1][j+1]==0) dfs2(i-1,j+1);      
}

int main()
{
    int t,i,j,k,e[50002][3],ans1,d;
    bool f;
    scanf("%d",&t);
    
    while(t--)
    {
        scanf("%d %d %d",&r,&c,&d);
        memset(cnt,0,sizeof(cnt));
        
        for(i=0;i<d;i++)
        scanf("%d %d %d",&e[i][0],&e[i][1],&e[i][2]);
        
        gets(s);
        for(i=0;i<r;i++)
        gets(arr[i]);
        
        ans=0;
        ans1=0;
        f=0;
        for(i=0;i<r;i++) 
        for(j=0;j<c;j++)
        {
            if(arr[i][j]=='#' && f==0)
            {
                dfs1(i,j);
                f=1;
            }
            if(arr[i][j]=='#')
            ans1++;
        }
        
        if(ans1!=ans)
        {
            puts("not solved");
            continue;
        }
        
        memset(cnt,0,sizeof(cnt));
        
        for(i=0;i<d;i++)
        {
            ans=0;
            dfs(e[i][0],e[i][1]);
            
            if(ans!=e[i][2])
            break;
        }
        
        if(i!=d)
        {
            puts("not solved");
            continue;
        }
        
        f=0;
        for(i=0;i<r-1;i++)
        {
            for(j=0;j<c-1;j++)
            {
                 if(arr[i][j]=='#' && arr[i+1][j]=='#' && arr[i+1][1+j]=='#' && arr[i][j+1]=='#')
                 {
                   f=1;
                   break;
                 }
            }
            
            if(f) break;
        }
        
        if(f)
        {
            puts("not solved");
            continue;
        }
        
        memset(cnt,0,sizeof(cnt));
        
        f=0;
        for(i=0;i<r;i++)
        {
              for(j=0;j<c;j++)
              {
                    if(arr[i][j]=='.' && cnt[i][j]==0)
                    {
                       fl=0;
                       dfs2(i,j);
                       if(fl==0)
                       {
                       f=1;
                       break;
                       }
                    }
              }
              if(f)
              break;
        }
        
        if(f)
        {
            puts("not solved");
            continue;
        }
        
        else
        {
            puts("solved");
        }
    }
    system("pause");
    return 0;
}

Chirag Chheda
Learning poster
Posts: 74
Joined: Sat Jun 21, 2008 12:24 pm
Location: India

Re: 11585 - Nurikabe

Post by Chirag Chheda » Tue Mar 10, 2009 12:59 pm

I have a doubt. Can thr be such type of input :-

Code: Select all

1
3 4 2
0 3 1
1 1 1
###.
#.##
.##.
the description tells that there are only 2 dots but there are 4 in the actual nurikabe.
If yes what should be the answer

User avatar
vahid sanei
Learning poster
Posts: 84
Joined: Fri Jan 09, 2009 4:37 pm
Location: IRAN

Re: 11585 - Nurikabe

Post by vahid sanei » Tue Mar 10, 2009 4:54 pm

Code: Select all

not solved
Impossible says I`m possible

Post Reply

Return to “Volume 115 (11500-11599)”