| ENG RUS | Timus Online Judge |
Обсуждение задачи 1033. ЛабиринтDmi3Molodov To admins: new task // Задача 1033. Лабиринт 3 янв 2025 05:41 For some, task No. 1033 seemed simple. A new task is offered especially for them (don't say it's difficult!) A multidimensional maze (also with wallpaper, walls and entrances). The input data consists of two sequences of numbers. The sign of the end of each sequence is zero (it is not part of the sequence). The first sequence: Guaranteed: the sum of the modules of the numbers does not exceed 1E+7. The number of negative numbers is equal to the number of entrances to the maze. The number of positive numbers is equal to the number of monolithic blocks of stone walls. Sk=The sum of the modules of the numbers from the beginning determines the unique number of the place in the maze. The second sequence is the numbers N[i] defining the sizes of the maze. Guaranteed: 1<N[i]<32 The length of the sequence (d) is equal to the dimension of the maze. These numbers themselves set the sizes of the maze according to the (i-th) coordinate. Knowing Sk, it is possible to determine all d coordinate values of a unique place in the maze. Sk=R[d]+1 where R[0]=0 and R[i+1]=R[i]*N[i]+THE_COORDINATE[i] Result: the same as in task No. 1033 P.S. Memory needed ~ 4Mb O(SM). Time limit - O(SM*log(SM)) where SM-the sum of the modules of the numbers Некоторым задача №1033 показалась простой. Специально для них предлагается новая задача (не говорите,что сложная!) Многомерный лабиринт (тоже с обоями,стенами и входами). Входные данные состоят из двух последовательностей чисел. Признак конца каждой последовательности - ноль(не является частью последовательности). Первая последовательнось: Гарантировано: сумма модулей чисел не превосходит 1Е+7. Количесво отрицательных чисел равно количеству входов в лабиринт. Количесво положительных чисел равно количеству монолитных блоков каменных стен. Sk=Сумма модулей чисел от начала определяет уникальный номер места в лабиринте. Вторая последовательность: Числа N[i] задающие размеры лабиринта. Гарантировано: 1<N[i]<32 Длина последовательности (d) равна размерности лабиринта. Сами эти числа задают размеры лабиринта по (i-той) координате. Зная Sk можно определить все d значений координат уникального места в лабиринте. Sk=R[d]+1 где R[0]=0 и R[i+1]=R[i]*N[i]+КООРДИНАТА[i] Результат: тот же что и в задаче №1033 P.S. Надеюсь, что удалось объяснить. Edited by author 03.01.2025 06:52 DonNTU Team (Akulshin, Belikov, Trofimenko) Finally I got AC!!! IF you have problems, read this text (I HAD WA5) [4] // Задача 1033. Лабиринт 29 авг 2006 15:03 I had this problems: 3 .## ### ##. answer is 36. If you have any problems write me john_chip<dog>mail.ru You can write russian messages footman_7 Re: Finally I got AC!!! IF you have problems, read this text (I HAD WA5) // Задача 1033. Лабиринт 4 апр 2011 07:22 Thank you. 1212166 Re: Finally I got AC!!! IF you have problems, read this text (I HAD WA5) // Задача 1033. Лабиринт 9 окт 2013 20:57 thank =D ayush vatsa Re: Finally I got AC!!! IF you have problems, read this text (I HAD WA5) [1] // Задача 1033. Лабиринт 15 май 2014 16:40 But,it's written in the question,only those wall will be wallpapered which are visible from one end.in you example if we enter from top left...the down right cell is not visible...so ans should be 18....correct me if i am wrong?? intensefrenemy4227 Re: Finally I got AC!!! IF you have problems, read this text (I HAD WA5) // Задача 1033. Лабиринт 8 сен 2024 01:27 I am 10 years late, but I hope you do read this, in the problem it states both the first and last cell are 'entrances', so you can enter via both cells. Cheers! iceswanX AC at last! [4] // Задача 1033. Лабиринт 3 мар 2005 09:05 i got WA because i don't realize that from the upper left to the bottom right there is no guarantee that they are connected. Daniel Re: AC at last! [3] // Задача 1033. Лабиринт 29 дек 2005 19:04 I also got WA because of it. I thought that upper left is entrance and bottom right is exit! AlainDelon Re: AC at last! // Задача 1033. Лабиринт 2 дек 2007 20:12 Oh, god! You guys are so smart! I ran into the same trap and got AC following your hints. Thanks a lot! Я крыса которая съест тебя! Re: AC at last! [1] // Задача 1033. Лабиринт 16 дек 2007 01:02 Yeah I thought same thing! waccub@gmail.com Re: AC at last! // Задача 1033. Лабиринт 24 авг 2023 14:22 I also had the same problem, 2 entrance one is upper left, one is lower right, both are open and no wall, :) (after spending more than 4 hour!) Marian Darius I GET WA1!!!!! [2] // Задача 1033. Лабиринт 2 ноя 2012 16:05 PLEASE TELL ME WHAT IS WRONG! I TRIED EVERYTHING!!! #include<stdio.h> #include<queue> using namespace std; struct Coord {int x,y;}; int a[40][40]; inline int number(int x,int y) { int nr=0; if(a[x+1][y]==-1) nr++; if(a[x-1][y]==-1) nr++; if(a[x][y+1]==-1) nr++; if(a[x][y-1]==-1) nr++; return nr; } Coord make(int a,int b) { Coord x; x.x=a;x.y=b; return x; } void lee(Coord s) { int x,y; queue<Coord> q; q.push(s); a[s.x][s.y]=1; while(!q.empty()) { x=q.front().x;y=q.front().y; if(a[x+1][y]==0) {a[x+1][y]=1;q.push(make(x+1,y));} if(a[x-1][y]==0) {a[x-1][y]=1;q.push(make(x-1,y));} if(a[x][y+1]==0) {a[x][y+1]=1;q.push(make(x,y+1));} if(a[x][y-1]==0) {a[x][y-1]=1;q.push(make(x,y-1));} q.pop(); } } int main() { int n,i,j;char ch; scanf("%d\n",&n); for(i=1;i<=n;i++,scanf("%c",&ch)) for(j=1;j<=n;j++) { scanf("%c",&ch); if(ch=='.') a[i][j]= 0; else a[i][j]=-1; } for(i=2;i<=n+1;i++) a[i][0]=a[0][i]=-1; for(i=0;i<n;i++) a[i][n+1]=a[n+1][i]=-1; lee(make(1,1)); lee(make(n,n)); int nr=0; for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(a[i][j]==1) nr+=number(i,j); printf("%d\n",9*nr); return 0; } gautamvs Re: I GET WA1!!!!! [1] // Задача 1033. Лабиринт 11 сен 2013 15:23 Is sample test case working for this program ? Hristo Nikolaev (B&W) Re: I GET WA1!!!!! // Задача 1033. Лабиринт 24 дек 2022 16:32 WA1 usually means the new lines ( \n ) or ( \r\n ) are not handled correctly. Hristo Nikolaev (B&W) Admins, make it 3 ≤ N ≤ 333 // Задача 1033. Лабиринт 24 дек 2022 16:30 Or at least add another version of the problem with huge labyrinths. I had a lot of fun with this problem, and was surprised that a solution which is far from perfect can work instantly with input 200x200. skyhoop if WA4 try this [4] // Задача 1033. Лабиринт 22 фев 2014 11:58 3 .## ### ##. Zearot Re: if WA4 try this // Задача 1033. Лабиринт 27 июл 2014 07:42 Thanks!This really helps. Insectophob Re: if WA4 try this // Задача 1033. Лабиринт 8 авг 2014 13:50 Thx a lot! But I thought the end of the labyrinth must be reachable from the beginning... jinyang Re: if WA4 try this [1] // Задача 1033. Лабиринт 29 авг 2014 15:28 Thank you~ Hristo Nikolaev (B&W) Re: if WA4 try this // Задача 1033. Лабиринт 24 дек 2022 16:19 Thank you! I also gathered the impression that 1,1 is the entrance, and n,n is the exit ... Without this misunderstanding, I would have had AC from the very first attempt. Cheers! vicodin why i always get "Runtime error (access violation)" on the test №1? // Задача 1033. Лабиринт 7 авг 2022 13:12 i found mistake :) Edited by author 07.08.2022 13:48 guilty spark What is up with multiplication by 9? [1] // Задача 1033. Лабиринт 29 авг 2020 12:54 I've noticed that the solution is always the number of walls we encounter*9 (excluding the first and last boxes). Why is this working? guilty spark Re: What is up with multiplication by 9? // Задача 1033. Лабиринт 29 авг 2020 13:01 I got it. The question asks for the area not the length ramil_xp Хуснутдинов Рамиль Give me Test 4 Please!! [22] // Задача 1033. Лабиринт 7 сен 2005 18:15 I am get WA on test 4. Macarie Re: Give me Test 4 Please!! [1] // Задача 1033. Лабиринт 8 сен 2005 13:18 33 .#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#. ................................# #.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.# ##.#.#.#.#.#.#.#.#.#.#.#.#.#.#... ...............................## #.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.# #..#.#.#.#.#.#.#.#.#.#.#.#.#.#... ................................# #.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.# ##.#.#.#.#.#.#.#.#.#.#.#.#.#.#... ...............................## #.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.# #..#.#.#.#.#.#.#.#.#.#.#.#.#.#... ................................# #.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.# ##.#.#.#.#.#.#.#.#.#.#.#.#.#.###. ................................# #.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.# #..#.#.#.#.#.#.#.#.#.#.#.#.#.#.#. ................................# #.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.# ##.#.#.#.#.#.#.#.#.#.#.#.#.#.#... ...............................## #.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.# #..#.#.#.#.#.#.#.#.#.#.#.#.#.#... ...............................## #.##.#.#.#.#.#.#.#.#.#.#.#.#.#... ................................# #.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.# #.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.# ##.#.#.#.#.#.#.#.#.#.#.#.#.#.#... ...............................## #.#.#.#.#.#.#.#.#.#.#.#.#.#.#.... answer: 12384 check other tests at timustests.lx.ro zzq Re: Give me Test 4 Please!!,but is wrong! // Задача 1033. Лабиринт 2 июл 2006 21:13 15: #.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.# 16: ##.#.#.#.#.#.#.#.#.#.#.#.#.#.###. 第15，16行之间不能连通！ zzq Re: Give me Test 4 Please!! [8] // Задача 1033. Лабиринт 2 июл 2006 21:15 I am get WA on test 4 too! test 4 is wrong! zzq Re: Give me Test 4 Please!! [7] // Задача 1033. Лабиринт 2 июл 2006 21:47 我知道TEST 4怎么WA的了！ 有几点要归纳出来： 1： ural 有保留字： Following words are reserved. For Pascal: as class dispose except exit exports false finalization finally initialization is library new on property raise true try 我就使用了"try"这个保留字，结果就编译错误了。 2： 第四个数据的底15，16行不能连通！ 所以：要从点（1，1）与点（N，N）分别搜索！（我是广搜） 如果只从点（1，1）开始搜，结果为：5760。 如果只从点（N，N）开始搜，结果为：6624。 两者之和正好是正确答案：12384 ！ 希望我写的这些对你有用！ IMS：WITHOUT WAX CS，HN，CHINA 2006，07，02 23：55 SM Re: Give me Test 4 Please!! // Задача 1033. Лабиринт 17 дек 2006 11:38 Thank you very much!You are so clever! StarForever Re: Give me Test 4 Please!! // Задача 1033. Лабиринт 29 дек 2006 12:21 .... 竟然可以打中文的.... veterinarian Re: Give me Test 4 Please!! // Задача 1033. Лабиринт 28 фев 2007 10:56 Thanks a million!!! Nickolas Kakà Re: Give me Test 4 Please!! // Задача 1033. Лабиринт 7 апр 2008 20:57 Ha! You're so helpful! yuhc Re: Give me Test 4 Please!! // Задача 1033. Лабиринт 14 май 2009 17:45 赞～！！中文太棒了～～ remdy21 Re: Give me Test 4 Please!! // Задача 1033. Лабиринт 3 авг 2009 19:49 thanks a lot!!!!!!!!!!!!!!!! :) fex Re: Give me Test 4 Please!! // Задача 1033. Лабиринт 16 окт 2017 18:31 you are so clever ! Thanks very much ! Liu Cong Re: Give me Test 4 Please!! [3] // Задача 1033. Лабиринт 30 июн 2007 07:56 可以中文？？？ Liu Strong Re: Give me Test 4 Please!! [2] // Задача 1033. Лабиринт 5 окт 2007 20:05 上面的几位聪明的中国大牛同胞，看没看见下面的Rules?明确写着“Messages should be written in English.(消息必须用英文写)”，请遵守规则，谢谢。 ------- To my clever Chinese friends above, didb't you see the Rules below? It says clearly that "Messages should be written in English." Please obey that. Thanks. Pegasus Re: Give me Test 4 Please!! [1] // Задача 1033. Лабиринт 6 апр 2013 11:54 You also used Chinese. Neznakomec Re: Give me Test 4 Please!! // Задача 1033. Лабиринт 15 июл 2013 00:47 Hah, i guessed myself that labyrinth can have no way from entrance to exit ) nub Re: Give me Test 4 Please!! [4] // Задача 1033. Лабиринт 23 ноя 2007 04:37 the thing is, there doesn't have to be a path from 1,1 to n,n, so you have to check both sides. Jim Liang Unidentified Re: Give me Test 4 Please!! // Задача 1033. Лабиринт 28 мар 2008 06:14 i got WA at test 4 ,too! thank you!! why cant't discussion be written in chinese or russia?? # Messages should NOT contain source code (especially correct solutions). why?? i think source code indeed may cause cheat,but someone who always gets WA really need them to improve Edited by author 28.03.2008 06:14 Edited by author 28.03.2008 06:15 SubmitRush Re: Give me Test 4 Please!! [1] // Задача 1033. Лабиринт 13 авг 2009 08:09 Good Point~ Thankx The reanson why Test#4 is valid is we can enter upper left as well as lower right. nub писал(a) 23 ноября 2007 04:37 the thing is, there doesn't have to be a path from 1,1 to n,n, so you have to check both sides. Edited by author 13.08.2009 08:22 Smilodon_am [Obninsk INPE] Re: Give me Test 4 Please!! // Задача 1033. Лабиринт 4 май 2011 17:35 Simple test for those who had WA #4: 3 ..# .#. #.. Answer is 108. Vlad Costin Re: Give me Test 4 Please!! // Задача 1033. Лабиринт 3 ноя 2017 22:50 Thank you very much! iamds Re: Give me Test 4 Please!! // Задача 1033. Лабиринт 21 окт 2011 16:43 Thanks! I got WA in test 4 too. Sergey Ubogov Re: Give me Test 4 Please!! // Задача 1033. Лабиринт 16 мар 2016 19:27 .#. .#. .#. answ 108 eurol test #1 run-time error // Задача 1033. Лабиринт 21 апр 2017 22:47 What is in #1??? Grandmaster Some tests // Задача 1033. Лабиринт 18 мар 2015 13:55 10 .......... #......#.. ...#...... ###..#...# ...#..##.. ......##.. ....#..### ...#..#.#. ..#####... ....#..... Answer 864 20 ..........#......#.. ...#......###..#...# ...#..##........##.. ....#..###...#..#.#. ..#####.......#..... ..#..#.#..#.###.##.. ...#.......#..#..... ..#.##...#...#.####. ..##.#....#....##... ...#..#.....###...#. #...###.##...#.##.#. .......#..#..##..... ...#...##........... .......###....#.###. #..###.#.#.#.......# .....#.##..#.#.####. #....##..#.#..#...#. ....#..#.###...#.##. .#.......#....#.#.## ......#.....#....... Answer 3222 33 ..........#......#.....#......### ..#...#...#..##........##......#. .###...#..#.#...#####.......#.... ...#..#.#..#.###.##.....#.......# ..#.......#.##...#...#.####...##. #....#....##......#..#.....###... #.#...###.##...#.##.#........#..# ..##........#...##............... ...###....#.###.#..###.#.#.#..... ..#.....#.##..#.#.####.#....##..# .#..#...#.....#..#.###...#.##..#. ......#.#..#.#.##......##....##.. .#.#.#..#.####.#..##.#..##....#.# ..#.#..#...#...#....#..#.....#... #....##....##.....#....#.#..#...# ..####...#..##.#..#......#.....#. ..#.####..#...#####...#....#.#.#. .......###.##.....#....##.#.#.#.. ..#.....#.##.#...#..#....#.#.#... #..##.#...#.......#.......#...#.. #...#..#.##.#.......#.##..####... .#....#..#####......#.#.###....#. ..#.#.#....#.#.#..##..#....#..##. .#..##...#.###..#.......###.#..## .#.#.....#..............###...#.. ..##...####.#.#..##.#.#....#...#. .....##...........#.#....#....##. ..##..#.####...#.##.....##.#..... .....#...........##.#.##.#.#...#. .#........#......##.....#..###.## ....##...#.#.#.#.######...#...#.. #...###..#....#.##.#...#.#......# .........##..##.##.........#..... Answer 8676 9 ..##.#### #.......# .#.##.##. ##..#.#.# ...#..#.. #......#. .....#..# #####..#. #.###.... Answer 576 Edited by author 18.03.2015 14:06 Maigo Akisame (maigoakisame@yahoo.com.cn) How to read input in Java? [4] // Задача 1033. Лабиринт 8 авг 2007 13:38 Is there a class or sth that can both read integers and single chars? Somebody please give me some example code. Thanks! BiTOk[PermSU] Re: How to read input in Java? // Задача 1033. Лабиринт 30 май 2009 23:56 I write this: import java.io.*; public class Main { static BufferedReader in; //........ public static void main(String[] args) throws IOException { in = new BufferedReader(new InputStreamReader(System.in)); PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out)); int n = Integer.parseInt(in.readLine()); //..... for(int i=1; i<n+1; i++){ for(int j=1; j<n+1; j++) { lab[i][j] = (char)in.read(); while(lab[i][j]!='#' && lab[i][j]!='.') lab[i][j] = (char)in.read(); //in win used two bytes end of line, in *NIX 1 byte } in.read(); } //..... u_saydazimov Re: How to read input in Java? [2] // Задача 1033. Лабиринт 2 окт 2010 09:32 import java.util.*; import java.io.*; public class Main{ public static void main(String[] argv) throws IOException{ new Main().run(); } PrintWriter pw; Scanner sc; public void run() throws IOException{ boolean oj = System.getProperty("ONLINE_JUDGE") != null; Reader reader = oj ? new InputStreamReader(System.in) : new FileReader("input.txt"); Writer writer = oj ? new OutputStreamWriter(System.out) : new FileWriter("output.txt"); sc = new Scanner(reader); pw = new PrintWriter(writer); int n = sc.nextInt(); int arr[][] = new int[n+2][n+2]; for(int i=1;i<=n;i++){ String str = sc.next(); for(int j=0;j<n;j++) if(str.charAt(j)=='.') arr[i][j+1] = 1; } //... pw.close(); } } Moonstone [Samara SAU] Re: How to read input in Java? [1] // Задача 1033. Лабиринт 2 окт 2010 12:03 The best template for Java: BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); PrintWriter out = new PrintWriter(System.out); StringTokenizer tok = null; String readToken() throws IOException { // reads the token; to read a full line use in.readLine() while (tok == null || !tok.hasMoreTokens()) { tok = new StringTokenizer(in.readLine()); } return tok.nextToken(); // sometimes it's better to use nextToken(String) method here } int readInt() throws IOException { // write readDouble(), readLong(), readBigInteger() methods if necessary return Integer.parseInt(readToken()); } SButterfly [Samara SAU] Re: How to read input in Java? // Задача 1033. Лабиринт 15 янв 2015 15:52 In addition to previouse answer char[] arr = readString().toCharArray(); //reads string and creates an array of characters. It works not so fast, but for small input, like this, it would be the quickest way to write a code. If you want to read for 1 char manual try this: char readChar() throws IOException{ int x = 0; while ((x = in.read()) == '\n' || x == '\r' || x == ' '){ } return (char)x; } RobertKhasanov WA 3 Help me [6] // Задача 1033. Лабиринт 14 дек 2006 22:04 All test in other topics is OK But my program WA on Test3. Why? Syu SeiMin Re: WA 3 Help me // Задача 1033. Лабиринт 24 мар 2009 10:28 [0..34,0..34]. evjava Re: WA 3 Help me [4] // Задача 1033. Лабиринт 4 ноя 2009 00:15 If you WA3, try use this test: 3 ... .#. ... my AC program give 108 It's may be help you if WA4 try 3 ... ### ... ans 108 too Edited by author 04.11.2009 00:17 Edited by author 04.11.2009 00:17 hinst Re: WA 3 Help me [2] // Задача 1033. Лабиринт 29 ноя 2009 20:34 i have the same problem. my WA#3 program give 108 on 3 ... .#. ... Mrw Re: WA 3 Help me [1] // Задача 1033. Лабиринт 23 фев 2010 13:28 I had have this probrom before I try WA4's test. 3 ... ### ... Answer is 108 WA5's test: 5 ..#.. ..#.. ##### ..#.. ..#.. Answer is 108 And there's a BIG TEST 33 ............#........#....##..... ....#..##.........#.....##..#.... .....#.##....#...........#.#####. #..###.....#..............#.....# ......##......#.##..#.....#.....# ###.##.#.........##.#.....#.#.#.. ..#..#.##......#.###.#.....#.###. ##.......##....#.#..##.##.#.#.... ....##.....#.............#..#.... #...###.###......#..#..#.....###. ##......##..#..#....#......###... .#...#.#..#######..#..####....... ....##.#.........##....##........ .......#...#......#....###....#.# ....#.#.........#.#..##......#... #..##..#...#.#..#.#####..##....#. #.....#......#.#..##.#...#.###... ..........#...#..##....##...#...# ..##.#..#...#..#..##............# ...........#..#.#.#....#.....##.. #.#.#...####..#...#..#....#.#.... .#.....#.#.......##.#.#.#...##.#. ..#..##....#.................#..# .......#..#.###......#.....#..... .#.......#.....#.....#........... ....#.####......#....###......... .#.#.##.#.....##..##........#.##. ..#......#.#.##....#......#.#.... #..........##....#.#..#####.#.... .....#..#.#.....###.....#...#.... #..........#..#.#...##........#.. .......#....#..#.........#....... .....#..#.......##.##..#......... ANSWER 7812 oybek Re: WA 3 Help me // Задача 1033. Лабиринт 30 авг 2014 19:34 My AC code gives 4626 for this test: 33 ............#........#....##..... ....#..##.........#.....##..#.... .....#.##....#...........#.#####. #..###.....#..............#.....# ......##......#.##..#.....#.....# ###.##.#.........##.#.....#.#.#.. ..#..#.##......#.###.#.....#.###. ##.......##....#.#..##.##.#.#.... ....##.....#.............#..#.... #...###.###......#..#..#.....###. ##......##..#..#....#......###... .#...#.#..#######..#..####....... ....##.#.........##....##........ .......#...#......#....###....#.# ....#.#.........#.#..##......#... #..##..#...#.#..#.#####..##....#. #.....#......#.#..##.#...#.###... ..........#...#..##....##...#...# ..##.#..#...#..#..##............# ...........#..#.#.#....#.....##.. #.#.#...####..#...#..#....#.#.... .#.....#.#.......##.#.#.#...##.#. ..#..##....#.................#..# .......#..#.###......#.....#..... .#.......#.....#.....#........... ....#.####......#....###......... .#.#.##.#.....##..##........#.##. ..#......#.#.##....#......#.#.... #..........##....#.#..#####.#.... .....#..#.#.....###.....#...#.... #..........#..#.#...##........#.. .......#....#..#.........#....... .....#..#.......##.##..#......... fytain Re: WA 3 Help me // Задача 1033. Лабиринт 27 июл 2013 20:29 thanks <<--Falcon-->> Need your help!!! [3] // Задача 1033. Лабиринт 24 ноя 2011 03:43 Hi,guys. This problem is quite interesting for me and I'd like to solve it, but, truth to tell, I don't know how... :( I know that the problem relates to the graph theory, but I can't figure out what the problem of the graph theory this problem represents and what algorithms can be applied here. So, could you give me some little hint how to solve the problem?... Please..... morbidel Re: Need your help!!! [2] // Задача 1033. Лабиринт 24 ноя 2011 05:21 Hi, Read about the Flood fill algorithm. For example here: http://en.wikipedia.org/wiki/Flood_fill Good luck! <<--Falcon-->> Re: Need your help!!! [1] // Задача 1033. Лабиринт 25 ноя 2011 15:34 Thank you very much for the info. Finally, I've got AC :)(It turned out to be a very easy problem). However, I still don't understand why this problem relates to the graph theory... Edited by author 25.11.2011 15:35 Andrew Sboev Re: Need your help!!! // Задача 1033. Лабиринт 3 июл 2012 21:19 Hmm. I used BFS to solve this problem, for example twinsclover just a possible test // Задача 1033. Лабиринт 11 окт 2010 18:42 5 .#### ..### ##### ##### ##... ans:108 me What's wrong with my input code? I always have WA #1 [1] // Задача 1033. Лабиринт 1 окт 2010 13:48 My program seems to work correctly on all tests I tried, including all the tests that could be found in topics of this problem's discussion. Nevertheless, I always have WA #1 when I submit it as a solution, so I guess something is wrong not with the algorithm, but with I/O code. Here it is (I know that the rules of the board deny posting code, but this is only input/output code, no part of algorithm is exposed): int main(int argc, char **argv){ int n; std::cin >> n; Labyrinth lab(n); for(int i = 0; i < n; i++){ std::string s; std::getline(std::cin, s); // strip the last linebreak, if any if(s[s.length() - 1] == '\n') s.resize(s.length() - 1); // if the string is empty // (for example, after reading the // number from the first line), // reread it (modifying the current line index) if(s.length() == 0) { i--; continue; } for(int j = 0; j < n; j++){ if(s[j] == '#') lab.add_wall_block(j, i); } } std::cout << 9 * lab.total_walls_visible() << std::endl; return 0; } (if the formatting is broken, here is the alternative: http://itpaste.ru/92461 ) Edited by author 01.10.2010 13:49 me Re: What's wrong with my input code? I always have WA #1 // Задача 1033. Лабиринт 1 окт 2010 14:37 Oops, I'm sorry, I got AC without any modifications of I/O code. The problem was rather unexpected though: I use g++ on 64-bit linux, and it aligns all the variables to the 8 byte blocks. There was one line in algorithm where I accessed the integer which was one-off the array. Because of the alignment, there was some free space after the array (silently initialized to zero by g++), so accessing the variable was harmless: I was reading the point to visit next, and I always got (0, 0) as the coordinate, which was to visit anyway. Timus's compiler works on 32-bit machine (as far as I know) and didn't align the array, so I was getting an invalid coordinate. Thanks to the valgrind, I found the problem. Tony Beta Lambda 3 is NOT the magic digit // Задача 1033. Лабиринт 18 мар 2010 10:50 7 is! Edited by author 18.03.2010 10:51 Olzhas aka Whale2dy Some info about this problem [3] // Задача 1033. Лабиринт 1 апр 2007 01:50 Hey, guys. Just wanted to share some information about this problem 1. If your program doesnt work on test #4, than probably the problem is - you "travel" only from the top left corner, but you should "travel" from the lower right corner also. (probably the reason why you should do this is that the labyrinth may be unfinished - sometimes the two ends of it are not connected) 2. If your program doesnt work on test #5 you can find on timustests.lx.ro Hope it will help somebody Ivanov Alexander Re: Some info about this problem // Задача 1033. Лабиринт 23 июн 2007 17:10 Thank you Javran Re: Some info about this problem // Задача 1033. Лабиринт 15 окт 2007 16:24 just work like this: floodfill(1,1); floodfill(n,n); ..... ...... and i got AC ^_^ evjava Re: Some info about this problem // Задача 1033. Лабиринт 4 ноя 2009 00:04 Thank you for site InShtein GREAT PROBLEM [1] // Задача 1033. Лабиринт 23 сен 2009 03:25 My program gets the right results on each test in discussion of the 1033 problem but I always get WA on test №1!!! My mind is broken... please whyyyy... What's the matter?! InShtein Re: GREAT PROBLEM // Задача 1033. Лабиринт 23 сен 2009 03:31 And the sample of problem is right too.... Ginforward I just wanna say... [2] // Задача 1033. Лабиринт 12 апр 2008 21:49 We have to think over the problem.. Actually..~the problem is so easy but.. some of us got WA at test#4(like me..)just because we hadn't thought about whether we could walk through the labyrinth from one exit to the other.. MarkoTanic Re: I just wanna say... [1] // Задача 1033. Лабиринт 15 апр 2008 02:39 We can enter the labyrith from the lower right entrance as well as from the upper left entrance. It seems to be the solution for our problems in test #4. SubmitRush Re: I just wanna say... // Задача 1033. Лабиринт 13 авг 2009 08:15 aha,,, Good insight~ : ) finally, I got the reason why Test#4 is valid. Thankx a lot~ MarkoTanic писал(a) 15 апреля 2008 02:39 We can enter the labyrith from the lower right entrance as well as from the upper left entrance. It seems to be the solution for our problems in test #4.
|