Definition: "inside the island"

Let's define the definition recursively:
1)If an island/sea touches the edge of the map, then it does not lie inside the sea/island

2)If an island/sea does not have internal seas/islands, then all the seas/islands it touches (it should be one if it does not touch the edge of the map) contain this island/sea inside themselves.

3)If an island/sea has internal seas/islands, then all these seas/islands in this island/sea, and all the seas of which these island/sea touch, which are not internal, contain this island/sea.

this all means that if the island lies inside the sea, which is inside the island, which is inside the sea, which is inside the island that touches the end of the map, and the illuminated sea is selected, the sea that is inside the island touching the map, then all the islands inside the sea are not part of the island touching the end of the map, and if the outer sea is selected, then since it is not exactly contains an island touching the map, then it should not contain islands inside this island

if you get runtime in c#, it's probably stack overflow. So use bfs instead of dfs, it helped me!

What's the meaning of "Land fragments that are adjacent to the map's
border are not considered as islands." ???

I can hardly understand it ! in the Example input, There is two
island adjacent to the map's border(the north-east corner and the
south-west corner) . but the answer is 3 !!! can anyone help me ?

My program gives correct answers for all the tests, but has WA#3. Swap(x,y) doesn't help :(
Give me, please, some unusual tests

Добрый день!
Я сдал эту задачу, и у меня возникли трудности с условием. Во-первых, нигде не написано, что такое "внутри моря". Во-вторых, когда я догадался до значения вышеупомянутого термина, я не уловил смысла в следующем предложении: "Острова, касающиеся границы карты, не могут быть использованы для захоронений шаманов – шаманы этого очень не любят". Острова, находящиеся на границе, точно не лежат внутри никакого моря. В связи с этим, у меня возникло предположение, что ответ на следующий тест - 1 (что вроде неверно):
5 7 1 1
.....
.####
.#...
.#.#.
.#...
.####
.....
(в ответ входит маленький островок справа). Поправьте условие, пожалуйста!

Help, please!!!

#include<stdio.h>
#include<iostream>
using namespace std;
const int maxn=505,maxq=50005;
const int  dx[9]={0,-1,1,0,0,-1,-1,1,1},dy[9]={0,0,0,-1,1,-1,1,1,-1};
const char sea='.',land='#',sea1=' ',land1='&';
char map[maxn][maxn];
int qx[maxq],qy[maxq],m,n,x,y,u,h,f,r,i,j;
int ans;
void init(){
     scanf("%d",&n);scanf("%d",&m);scanf("%d",&y);scanf("%d",&x);
     for(i=0;i<=n+1;i++)map[0][i]=land,map[m+1][i]=land;
     for(i=1;i<=m;i++)map[i][0]=land,map[i][n+1]=land;
     for(i=1;i<=m;i++)cin>>(map[i]+1);
}
void floodfill(int x,int y,char c1,char c2,char c3,int dir){
     int  i;
     f=0;r=1;qx[1]=x;qy[1]=y;map[x][y]=c3;
     do{
        f++;if(f>maxq)f=1;
        for(i=1;i<=dir;i++)
          if(map[qx[f]+dx[i]][qy[f]+dy[i]]==c1||map[qx[f]+dx[i]][qy[f]+dy[i]]==c2)
          {r++;if(r>maxq)r=1;qx[r]=qx[f]+dx[i];qy[r]=qy[f]+dy[i];map[qx[r]][qy[r]]=c3;}
        }while(f!=r);
}
void work(){
     floodfill(x,y,sea,sea,sea1,8);
     floodfill(0,0,sea,land,land1,4);
     for(int i=1;i<=m;i++)
       for(int j=1;j<=n;j++)
         if(map[i][j]==land){ans++;floodfill(i,j,land,land,land1,4);}
}
void print(){
     printf("%d\n",ans);
}
int main(){
    init();
    work();
    print();
    return 0;
}

This test I'm draw in paint :)

64 64 44 21
................................................................
.#######################################........................
.#.....................................#........................
.#.....................................#........................
.#.....................................#........................
.#.....................................#........................
.#.....................................#........................
.#.....................................#........................
.#.....................................#........................
.#.....................................#........................
.#.....................................#........................
.#..........###......................###........................
.#..........#.#......................#..........................
.#..........#.#......................#..........................
.#.........#..######################.#..........................
.#.........#.......................#.#..........................
.#.........#.#####################.#.#..........................
.#.........#.#...................#.#.#..........................
.#.........#.#.#################.#.#.#..........###############.
.#..########.#.#...............#.#.#.#..........#.............#.
.#..#........#.#...............#.#.#.#..........#.#############.
.#..#.######.#.#.....###.#####.#.#.#.#..........#.#...........#.
.#..#.#....#.#.#.###.#.#.#...#.#.#.#.#..........#.#........#..#.
.#..#.#....#.#.#.#.#.#.#.#...#.#.#.#.#..........#.#..#######..#.
.#..#.#.##.#.#.#.#.#.#.#.#...#.#.#.#.############.#........#..#.
.#..#.#..#.#.#.#.#.#.#.#.#...#.#.#.#.#............#........#..#.
.#..#.#.##.#.#.#.#.#.#.#.###.#.#.#.#.#.##########.#...######..#.
.#..#.#.#..#.#.#.#.#.#.#...#.#.#.#.#.#......#...#.#.###.......#.
.#..#.#.##.#.#.#.#.#.#.#.#.#.#.#.#.#.######.#...#.#...#.###...#.
.#..#.#..#.#.#.#.#.#.#.#...#.#.#.#.#.#....#.#...#.#...#...#...#.
.#..#.#.##.#.#.#.#.#.#.###.#.#.#.#.#.######.#...#.#...######..#.
.#..#.#.#..#.#.#.#.#.#...#.#.#.#.#.#........#...#.#.......#...#.
.#..#.#.##.#.#.###.###.#.#.#.###.#.#.#####.##...#.#..####.#...#.
.#..#.#..#.#.#...........#.#.....#.#.#...#.#....#.#..#..#.#...#.
.#..#.#.##.#.#############.#####.#.#.#...#.#....#.#..#....#...#.
.#..#.#.#..#...................#.#.#.#...#.#....#.#..######...#.
.#..#.#.##.###################.#.#.#.#...#.#....#.#...........#.
.#..#.#..#...................#.#.#.#.#...#.#....#.#.#########.#.
.#..#.#..###################.#.#.#.#.#...#.#....#.#.....#.....#.
.#..#.#......................#.###.#.#...#.#....#.#..#..####..#.
.#..#.#.###################..#.....#.#...#.#....#.#..##....#..#.
.#..#.#.#.................#..#.....#.#...#.#....#.#..#...#.#..#.
.#..#.#.#.................#..#.....#.#...#.#....#.#..####..#..#.
.#..#.#.#...............#.#..#.....#.#...#.#....#.#.....####..#.
.#..#.#.#.###############.####.....#.#...#.#....#.............#.
.#..#.#.#.#.............#..........#.#...#.#....#.............#.
.#..#.#.#.#.............#..#########.#...#.#....#.............#.
.#..#.#.#.#.###########.#..#.........#...#.#....###############.
.#..#.#.###.#.........#.#..#.#######.#...#.#....................
.#..#.#.....#.#########.#..#.......#.#...#.####################.
.#..#.#.................#..#..######.#...#....................#.
.#..#.###################..#..#......#...###########..........#.
.#..#......................#..######.#.............#.#.######.#.
.#..########################.........#....####.....#.#......#.#.
.#............................########...##..#.....#.#.####.#.#.
.##############################.........##...#.....#.#.#..#.#.#.
........................................#..#.#.....#.#.#..#.#.#.
..........................................##.#.....#.#.#..#.#.#.
...........................................#.#.....#.#.##...#.#.
...........................................###.....#.#......#.#.
...................................................#.########.#.
...................................................#..........#.
...................................................##########.#.
................................................................

My AC program write 15. Good luck!

Edited by author 01.02.2009 23:55

Edited by author 21.09.2008 23:43

Edited by author 21.09.2008 23:43

Is there any other way to solve this problem, please help me, give me
a tip.

Shaman, may be, drown in the land!
If place where he drown is land you must write '0'

9 7 1 1
........#
.########
.#.....#.
.#.#.#.#.
.#.....#.
.#######.
#........

If the sea isn't closed (Can it be?) what should i output?
For example
9 7 1 1
........#
.########
.#.....#.
.#.#.#.#.
.#.....#.
.#######.
#........

Is the answer 0 or 2?
Thanks.

Edited by author 15.05.2006 18:15

My program has WA#14. Breaking at me a mistake?
Who can help me? I shall be very grateful.
Give me the tests. Me the test, when the sea not closed interests. Somebody can answer this question? Please help. Here my tests with answers of my program:
1 Test:
9 7 1 1
........#
.########
.#.....#.
.#.#.#.#.
.#.....#.
.#######.
#........
The answer: 0
2 Test:
12 8 2 2
############
#...#......#
#...#.....##
###.#.#.####
#.#.#.#...##
#..##..##..#
#..........#
############
The answer: 2
3 Test:
6 6 3 4
######
#....#
#....#
#....#
#....#
######
The answer: 0
4 Test:
12 10 2 3
#######....#
#....##....#
#....##....#
#....##....#
#....##....#
#....##....#
#..........#
#....#..#.#.
############
#....###...#
The answer: 0
5 Test:
12 10 3 4
#######....#
#....##..#.#
#....##.#..#
#....##....#
#....##..#.#
#..#.##....#
#.#........#
#....#..#.#.
############
#....###...#
The answer: 5

Please help, please......
Thanks beforehand

I always WA......Help me,please...

What's the meaning of "Land fragments that are adjacent to the map's
border are not considered as islands." ???

I can hardly understand it ! in the Example input, There is two
island adjacent to the map's border(the north-east corner and the
south-west corner) . but the answer is 3 !!! can anyone help me ?

Const Size      = 500+1;
      Dx        : Array[1..8] of Integer=(0,0,-1,1,-1,1,-1,1);
      Dy        : Array[1..8] of Integer=(-1,1,0,0,-1,1,1,-1);

Type mapType    = Array[0..Size,0..Size] of Char;
     BType      = Array[0..Size,0..Size] of Byte;
     setType    = Set of Char;
     arr        = array[1..Size*8,1..2] of Integer;

Var  map        : mapType;
     n,m        : Integer;
     seax,seay  : Integer;

     b          : Btype;
     ans        : Integer;

Procedure Read_data;
Var  i,j        : Integer;
     temp       : Char;
Begin
  Fillchar(b,sizeof(b),0);
  Fillchar(map,sizeof(map),0);
  Readln(m,n,seay,seax);
  For i := 1 to N do Begin
    For j := 1 to M do
      Read(map[i,j]);
    Readln;
  End;
End;

Procedure Mark(x,y : Integer;mapset : setType;t_d : Integer);
Var q              : array[0..1] of arr;
    t              : array[0..1] of Integer;
    p,i,j,tx,ty    : Integer;
Begin
  If b[x,y]<>0 then Exit
               else b[x,y] := 1;
  t[0] := 1; p := 0;
  q[0][1,1] := x; q[0][1,2] := y;
  While t[p]>0 do Begin
    t[1-p] := 0;
    For i := 1 to t[p] do
      For j := 1 to t_d do Begin
        tx := q[p][i,1]+dx[j]; ty := q[p][i,2]+dy[j];
        If (tx>0) and (tx<=N) and (ty>0) and (ty<=M) and
           (b[tx,ty]=0) and (map[tx,ty] in mapset) then Begin
          Inc(t[1-p]);
          q[1-p][t[1-p],1] := tx;
          q[1-p][t[1-p],2] := ty;
          b[tx,ty] := 1;
        End;
      End;
    p := 1-p;
  End;
End;

Procedure Solve;
Var i,j         : Integer;
    mapset      : setType;
Begin
  ans := 0;
  If map[seax,seay]<>'.' then Exit;
  mapset := ['.'];
  Mark(seax,seay,mapset,8);

  mapset := ['#','.'];
  For i := 1 to N do
    For j := 1 to M do
      If b[i,j]=0 then
        If (i=1) or (i=N) or (j=1) or (j=M) then
          Mark(i,j,mapset,4);

  mapset := ['#'];
  For i := 1 to N do
    For j := 1 to M do
      If (map[i,j]='#') and (b[i,j]=0) then Begin
        Inc(ans);
        Mark(i,j,mapset,4);
      End;
End;

Begin
  Read_data;
  Solve;
  Writeln(ans);
End.

var
mapa:array[0..501,0..501]of -2..1;
x,y,wsp1,wsp2:longint;
ilewysp:longint;

procedure wczytaj;
var i,j:longint;
    zn:char;
    zb:text;
begin
 {assign(zb,'1250.in');
 reset(zb);     }
 readln({zb,}x,y,wsp1,wsp2);
 for i:=1 to y do
 begin
  for j:=1 to x do
   begin
   read({zb,}zn);
   if zn='#'then mapa[i,j]:=1
   end;
 readln{(zb)}
 end;
{close(zb)}
end;

procedure zaznacz(a,b:longint);
begin
mapa[a,b]:=-2;
 if (a-1>0)and(mapa[a-1,b]>0)then zaznacz(a-1,b);
 if (a+1<=x)and(mapa[a+1,b]>0)then zaznacz(a+1,b);
 if (b-1>0)and(mapa[a,b-1]>0)then zaznacz(a,b-1);
 if (b+1<=y)and(mapa[a,b+1]>0)then zaznacz(a,b+1);
end;

procedure sprawdz(a,b:longint);
begin
mapa[a,b]:=-2;
 if (a-1>0)and(mapa[a-1,b]>0)then zaznacz(a-1,b);
 if (a+1<=x)and(mapa[a+1,b]>0)then zaznacz(a+1,b);
 if (b-1>0)and(mapa[a,b-1]>0)then zaznacz(a,b-1);
 if (b+1<=y)and(mapa[a,b+1]>0)then zaznacz(a,b+1);
inc(ilewysp)
end;

procedure dfs(a,b:longint);
begin
mapa[a,b]:=-1;
 if (a-1>0)and(mapa[a-1,b]=0)then dfs(a-1,b)
 else if (a-1>0)and(mapa[a-1,b]=1)then sprawdz(a-1,b);

 if (a+1<=x)and(mapa[a+1,b]=0)then dfs(a+1,b)
 else if (a+1<=x)and(mapa[a+1,b]=1)then sprawdz(a+1,b);

 if (b-1>0)and(mapa[a,b-1]=0)then dfs(a,b-1)
 else if (b-1>0)and(mapa[a,b-1]=1)then sprawdz(a,b-1);

 if (b+1<=y)and(mapa[a,b+1]=0)then dfs(a,b+1)
 else if (b+1<=y)and(mapa[a,b+1]=1)then sprawdz(a,b+1);
end;

begin
while not eof do
begin
fillchar(mapa,sizeof(mapa),0);
wczytaj;
dfs(wsp1,wsp2);
writeln(ilewysp)
end
end.