| Show all threads Hide all threads Show all messages Hide all messages |
| AC at last! | iceswanX | 1033. Labyrinth | 24 Aug 2023 14:22 | 5 |
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. I also got WA because of it.
I thought that upper left is
entrance and bottom right is
exit! Oh, god! You guys are so smart! I ran into the same trap and got AC following your hints.
Thanks a lot! Yeah I thought same thing! 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!) |
| I GET WA1!!!!! | Marian Darius | 1033. Labyrinth | 24 Dec 2022 16:32 | 3 |
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;
} Is sample test case working for this program ? WA1 usually means the new lines ( \n ) or ( \r\n ) are not handled correctly. |
| Admins, make it 3 ≤ N ≤ 333 | Hristo Nikolaev (B&W) | 1033. Labyrinth | 24 Dec 2022 16:30 | 1 |
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. |
| if WA4 try this | skyhoop | 1033. Labyrinth | 24 Dec 2022 16:19 | 5 |
Thanks!This really helps. Thx a lot! But I thought the end of the labyrinth must be reachable from the beginning... 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! |
| why i always get "Runtime error (access violation)" on the test №1? | vicodin | 1033. Labyrinth | 7 Aug 2022 13:12 | 1 |
i found mistake :)
Edited by author 07.08.2022 13:48 |
| What is up with multiplication by 9? | guilty spark | 1033. Labyrinth | 29 Aug 2020 13:01 | 2 |
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? I got it. The question asks for the area not the length |
| Give me Test 4 Please!! | ramil_xp Хуснутдинов Рамиль | 1033. Labyrinth | 3 Nov 2017 22:50 | 23 |
33
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
................................#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
##.#.#.#.#.#.#.#.#.#.#.#.#.#.#...
...............................##
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
#..#.#.#.#.#.#.#.#.#.#.#.#.#.#...
................................#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
##.#.#.#.#.#.#.#.#.#.#.#.#.#.#...
...............................##
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
#..#.#.#.#.#.#.#.#.#.#.#.#.#.#...
................................#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
##.#.#.#.#.#.#.#.#.#.#.#.#.#.###.
................................#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
#..#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
................................#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
##.#.#.#.#.#.#.#.#.#.#.#.#.#.#...
...............................##
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
#..#.#.#.#.#.#.#.#.#.#.#.#.#.#...
...............................##
#.##.#.#.#.#.#.#.#.#.#.#.#.#.#...
................................#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
##.#.#.#.#.#.#.#.#.#.#.#.#.#.#...
...............................##
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#....
answer: 12384
check other tests at timustests.lx.ro 15: #.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
16: ##.#.#.#.#.#.#.#.#.#.#.#.#.#.###.
第15，16行之间不能连通！ I am get WA on test 4 too!
test 4 is wrong! 我知道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
Thank you very much!You are so clever! thanks a lot!!!!!!!!!!!!!!!! :) you are so clever ! Thanks very much ! 上面的几位聪明的中国大牛同胞，看没看见下面的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. Hah, i guessed myself that labyrinth can have no way from entrance to exit ) the thing is, there doesn't have to be a path from 1,1 to n,n, so you have to check both sides. 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 Good Point~ Thankx The reanson why Test#4 is valid is we can enter upper left as well as lower right. 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:22Simple test for those who had WA #4:
3
..#
.#.
#..
Answer is 108. Thanks! I got WA in test 4 too. |
| test #1 run-time error | eurol | 1033. Labyrinth | 21 Apr 2017 22:47 | 1 |
|
| Some tests | Grandmaster | 1033. Labyrinth | 18 Mar 2015 13:55 | 1 |
10
..........
#......#..
...#......
###..#...#
...#..##..
......##..
....#..###
...#..#.#.
..#####...
....#.....
Answer 864
20
..........#......#..
...#......###..#...#
...#..##........##..
....#..###...#..#.#.
..#####.......#.....
..#..#.#..#.###.##..
...#.......#..#.....
..#.##...#...#.####.
..##.#....#....##...
...#..#.....###...#.
#...###.##...#.##.#.
.......#..#..##.....
...#...##...........
.......###....#.###.
#..###.#.#.#.......#
.....#.##..#.#.####.
#....##..#.#..#...#.
....#..#.###...#.##.
.#.......#....#.#.##
......#.....#.......
Answer 3222
33
..........#......#.....#......###
..#...#...#..##........##......#.
.###...#..#.#...#####.......#....
...#..#.#..#.###.##.....#.......#
..#.......#.##...#...#.####...##.
#....#....##......#..#.....###...
#.#...###.##...#.##.#........#..#
..##........#...##...............
...###....#.###.#..###.#.#.#.....
..#.....#.##..#.#.####.#....##..#
.#..#...#.....#..#.###...#.##..#.
......#.#..#.#.##......##....##..
.#.#.#..#.####.#..##.#..##....#.#
..#.#..#...#...#....#..#.....#...
#....##....##.....#....#.#..#...#
..####...#..##.#..#......#.....#.
..#.####..#...#####...#....#.#.#.
.......###.##.....#....##.#.#.#..
..#.....#.##.#...#..#....#.#.#...
#..##.#...#.......#.......#...#..
#...#..#.##.#.......#.##..####...
.#....#..#####......#.#.###....#.
..#.#.#....#.#.#..##..#....#..##.
.#..##...#.###..#.......###.#..##
.#.#.....#..............###...#..
..##...####.#.#..##.#.#....#...#.
.....##...........#.#....#....##.
..##..#.####...#.##.....##.#.....
.....#...........##.#.##.#.#...#.
.#........#......##.....#..###.##
....##...#.#.#.#.######...#...#..
#...###..#....#.##.#...#.#......#
.........##..##.##.........#.....
Answer 8676
9
..##.####
#.......#
.#.##.##.
##..#.#.#
...#..#..
#......#.
.....#..#
#####..#.
#.###....
Answer 576
Edited by author 18.03.2015 14:06 |
| How to read input in Java? | Maigo Akisame (maigoakisame@yahoo.com.cn) | 1033. Labyrinth | 15 Jan 2015 15:52 | 5 |
Is there a class or sth that can both read integers and single chars? Somebody please give me some example code. Thanks! 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();
}
//..... 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();
}
} 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());
} 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;
} |
| WA 3 Help me | RobertKhasanov | 1033. Labyrinth | 30 Aug 2014 19:34 | 7 |
All test in other topics is OK
But my program WA on Test3.
Why? 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 i have the same problem.
my WA#3 program give 108 on
3
...
.#.
... 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 My AC code gives 4626
for this test:
33
............#........#....##.....
....#..##.........#.....##..#....
.....#.##....#...........#.#####.
#..###.....#..............#.....#
......##......#.##..#.....#.....#
###.##.#.........##.#.....#.#.#..
..#..#.##......#.###.#.....#.###.
##.......##....#.#..##.##.#.#....
....##.....#.............#..#....
#...###.###......#..#..#.....###.
##......##..#..#....#......###...
.#...#.#..#######..#..####.......
....##.#.........##....##........
.......#...#......#....###....#.#
....#.#.........#.#..##......#...
#..##..#...#.#..#.#####..##....#.
#.....#......#.#..##.#...#.###...
..........#...#..##....##...#...#
..##.#..#...#..#..##............#
...........#..#.#.#....#.....##..
#.#.#...####..#...#..#....#.#....
.#.....#.#.......##.#.#.#...##.#.
..#..##....#.................#..#
.......#..#.###......#.....#.....
.#.......#.....#.....#...........
....#.####......#....###.........
.#.#.##.#.....##..##........#.##.
..#......#.#.##....#......#.#....
#..........##....#.#..#####.#....
.....#..#.#.....###.....#...#....
#..........#..#.#...##........#..
.......#....#..#.........#.......
.....#..#.......##.##..#......... |
| Finally I got AC!!! IF you have problems, read this text (I HAD WA5) | DonNTU Team (Akulshin, Belikov, Trofimenko) | 1033. Labyrinth | 15 May 2014 16:40 | 4 |
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 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?? |
| Need your help!!! | <<--Falcon-->> | 1033. Labyrinth | 3 Jul 2012 21:19 | 4 |
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..... 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 Hmm. I used BFS to solve this problem, for example |
| just a possible test | twinsclover | 1033. Labyrinth | 11 Oct 2010 18:42 | 1 |
5
.####
..###
#####
#####
##...
ans:108 |
| What's wrong with my input code? I always have WA #1 | me | 1033. Labyrinth | 1 Oct 2010 14:37 | 2 |
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:49Oops, 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. |
| 3 is NOT the magic digit | Tony Beta Lambda | 1033. Labyrinth | 18 Mar 2010 10:50 | 1 |
7 is!
Edited by author 18.03.2010 10:51 |
| Some info about this problem | Olzhas aka Whale2dy | 1033. Labyrinth | 4 Nov 2009 00:04 | 4 |
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 just work like this:
floodfill(1,1);
floodfill(n,n);
.....
......
and i got AC ^_^ |
| GREAT PROBLEM | InShtein | 1033. Labyrinth | 23 Sep 2009 03:31 | 2 |
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?! And the sample of problem is right too.... |
| I just wanna say... | Ginforward | 1033. Labyrinth | 13 Aug 2009 08:15 | 3 |
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..
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. aha,,, Good insight~ : ) finally, I got the reason why Test#4 is valid. Thankx a lot~ 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. |
| Give the help of tast 5!!!!!!!!!!!!!!!! | wutaibang | 1033. Labyrinth | 12 Apr 2008 14:05 | 1 |
|
