Show all threads Hide all threads Show all messages Hide all messages | This help understand statement about islands | 👑TIMOFEY👑 | 1250. Sea Burial | 7 Jan 2023 18:47 | 1 | 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 | runtime c# | Gerasimov Alexander Dmitrievich | 1250. Sea Burial | 18 Apr 2022 22:56 | 1 | runtime c# Gerasimov Alexander Dmitrievich 18 Apr 2022 22:56 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." ??? | XueMao | 1250. Sea Burial | 9 Dec 2018 18:40 | 3 | 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 ? In the first sample I checked the sacred islands' territory as '*': ........# .*******. .*.....*. .*.*.*.*. .*.....*. .*******. #........ So, there are 3 sacred islands. The land fragments in the corners of the map are not the islands, because they are adjacent to the map's border. but those islands are not in the same sea | WA#3 :( | Velter->ONPU | 1250. Sea Burial | 3 Jul 2014 02:58 | 1 | WA#3 :( Velter->ONPU 3 Jul 2014 02:58 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 | I use 'array[500,500]',then use dispose,Why momery limited? | Lin | 1250. Sea Burial | 25 Nov 2012 01:45 | 2 | Maybe you use recursion fill field? | Странное условие. | -XraY- | 1250. Sea Burial | 9 Sep 2012 19:35 | 1 | Добрый день! Я сдал эту задачу, и у меня возникли трудности с условием. Во-первых, нигде не написано, что такое "внутри моря". Во-вторых, когда я догадался до значения вышеупомянутого термина, я не уловил смысла в следующем предложении: "Острова, касающиеся границы карты, не могут быть использованы для захоронений шаманов – шаманы этого очень не любят". Острова, находящиеся на границе, точно не лежат внутри никакого моря. В связи с этим, у меня возникло предположение, что ответ на следующий тест - 1 (что вроде неверно): 5 7 1 1 ..... .#### .#... .#.#. .#... .#### ..... (в ответ входит маленький островок справа). Поправьте условие, пожалуйста! | Under what condition is the island in the sea? (Pri kakom uslovii ostrov nahoditsa v more?) | (<vav>) | 1250. Sea Burial | 2 Jul 2011 02:07 | 1 | | What's wrong with my program??? I want TEST #12 of Problem 1250 | lixiang | 1250. Sea Burial | 27 Jun 2011 14:40 | 2 | #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; } Apply the GOOD JOB for College ACMers to Make Large Money and Become a Millionaire Hello, We need large no. of dedicated and hard working ACMers. The payment is good so we need ACMers to be efficient. All you have to do to get the job is to sign up at our websites. The link of our websites are given below. http://www.PaisaLive.com/register.asp?3556638-4847933 After the registration, a confirmation email will be sent to your specified email address. Please click on the link inside the confirmation email to activate your account and recieve ACM work instantly. For any other queries you can mail the administrator. Miss Juliet Admin paisalive.com | if you have WA#3 swap x and y. | hoan | 1250. Sea Burial | 1 Dec 2010 18:04 | 1 | | Big test | OpenGL | 1250. Sea Burial | 2 Feb 2009 00:43 | 2 | 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 | I AC! | Piratek-(akaDK) | 1250. Sea Burial | 21 Sep 2008 23:20 | 1 | I AC! Piratek-(akaDK) 21 Sep 2008 23:20 Edited by author 21.09.2008 23:43 Edited by author 21.09.2008 23:43 | I solve it with BFS, but i still have Time Limit Exceeded. | rafal | 1250. Sea Burial | 5 Aug 2008 16:42 | 3 | Is there any other way to solve this problem, please help me, give me a tip. > Is there any other way to solve this problem, please help me, give me > a tip. BFS is O(N) and reading input is also O(N), so... | One trip | X | 1250. Sea Burial | 5 Aug 2008 16:42 | 3 | Shaman, may be, drown in the land! If place where he drown is land you must write '0' Not sure if it's true, but my AC solution will output 0 for that. | Please, help me! What's the output for this case? | plg | 1250. Sea Burial | 5 Aug 2008 16:41 | 3 | 9 7 1 1 ........# .######## .#.....#. .#.#.#.#. .#.....#. .#######. #........ | What output must be if the sea is not closed? Tell me answer for this test... | Alexey | 1250. Sea Burial | 5 Aug 2008 16:40 | 4 | 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 So, If the sea isn't closed, the answer must be 0? No, it still may have islands. Just islands that are inside border land do not belong to any outer sea, but there can be others. | My program has WA#14 | Zubyk Taras(Khmelnitsky) | 1250. Sea Burial | 5 Aug 2008 16:38 | 3 | 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 Try such test: 18 14 12 3 ........#........# .#######..#######. .#.....#..#.....#. .#.#.#.#..#.#.#.#. .#.....#..#.....#. .#######..#######. #........#........ ........#........# .#######..#######. .#.....#..#.....#. .#.#.#.#..#.#.#.#. .#.....#..#.....#. .#######..#######. #........#........ Answer is 2 (oops, that helped me with WA4 :) | Eagerly want TEST #3 Of Problem 1250 | xiaomengxian | 1250. Sea Burial | 21 Nov 2006 18:58 | 2 | I always WA......Help me,please... If you used read(x, y). Please use read(y, x) | What's the meaning of "Land fragments that are adjacent to the map's border are not considered as islands." ??? | XueMao | 1250. Sea Burial | 25 Jan 2006 00:11 | 2 | 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 ? Third island is rectangular border in the centre | what's wrong with my program? | Lin | 1250. Sea Burial | 21 Mar 2003 17:49 | 1 | 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. | What's wrong with that code ?? -> it's so obvious | uuuuuuu | 1250. Sea Burial | 16 Mar 2003 21:02 | 1 | 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. |
|
|