11585 - Nurikabe
Moderator: Board moderators
11585 - Nurikabe
Please explain me why in second example the answer is "not solved"???
3#1#2
.###.
.#1##
####3
2.#..
3#1#2
.###.
.#1##
####3
2.#..
-
- New poster
- Posts: 20
- Joined: Mon Oct 20, 2008 6:26 am
Re: 11585 - Nurikabe
"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. "
Re: 11585 - Nurikabe
I understood, that I don't understand this statement
!
Could you please show me in the figure above, where is a mistake...
![:D](./images/smilies/icon_biggrin.gif)
Could you please show me in the figure above, where is a mistake...
Re: 11585 - Nurikabe
Code: Select all
3#1#2
.###.
.#1##
####3
2.#..
-
- Learning poster
- Posts: 84
- Joined: Fri Jan 09, 2009 4:37 pm
- Location: IRAN
Re: 11585 - Nurikabe
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
i use bfs for this problem but i got acc in 0,540 , how can i reduce time of my code ?
![:-?](./images/smilies/icon_confused.gif)
thanks in advance
Impossible says I`m possible
Re: 11585 - Nurikabe
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.
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
![:)](./images/smilies/icon_smile.gif)
You can also speed up by using efficient methods for reading the input.
-
- Learning poster
- Posts: 84
- Joined: Fri Jan 09, 2009 4:37 pm
- Location: IRAN
Re: 11585 - Nurikabe
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
#
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
#
-
- Learning poster
- Posts: 84
- Joined: Fri Jan 09, 2009 4:37 pm
- Location: IRAN
Re: 11585 - Nurikabe
Input
Output
Code: Select all
4
1 2 0
##
1 1 0
.
1 1 0
#
1 2 1
0 0 1
.#
Code: Select all
not solved
not solved
not solved
solved
Impossible says I`m possible
Re: 11585 - Nurikabe
Finally accepted!!!!!
But my ac prog gives such answer on my test:
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
-
- Learning poster
- Posts: 84
- Joined: Fri Jan 09, 2009 4:37 pm
- Location: IRAN
Re: 11585 - Nurikabe
those arent 2 x 2 subsquare but i checkedin every 2 x 2 subsquare there is at least one unshaded space.
Impossible says I`m possible
-
- Learning poster
- Posts: 74
- Joined: Sat Jun 21, 2008 12:24 pm
- Location: India
Re: 11585 - Nurikabe
I am getting WA for this problem. I cant find my mistake. Can someone help me??
![:oops:](./images/smilies/icon_redface.gif)
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;
}
-
- Learning poster
- Posts: 74
- Joined: Sat Jun 21, 2008 12:24 pm
- Location: India
Re: 11585 - Nurikabe
I have a doubt. Can thr be such type of input :-
the description tells that there are only 2 dots but there are 4 in the actual nurikabe.
If yes what should be the answer
Code: Select all
1
3 4 2
0 3 1
1 1 1
###.
#.##
.##.
If yes what should be the answer
-
- Learning poster
- Posts: 84
- Joined: Fri Jan 09, 2009 4:37 pm
- Location: IRAN