Обсуждение @ 1254. Крепкий орешек @ Timus Online Judge

Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения
Страница 2
WA7	👑TIMOFEY👑	1254. Крепкий орешек	26 июн 2023 19:02	1
WA7 👑TIMOFEY👑 26 июн 2023 19:02 you don't know how to write bfs, try watching videos for beginners
WA6	👑TIMOFEY👑	1254. Крепкий орешек	26 июн 2023 18:40	1
WA6 👑TIMOFEY👑 26 июн 2023 18:40 precision
wa 9	Abid29	1254. Крепкий орешек	24 апр 2021 00:07	1
wa 9 Abid29 24 апр 2021 00:07 use sqrt(2.00) instead of 1.41421356
can anyone give a counterexample if BFS is wrong?	kerpoo	1254. Крепкий орешек	11 сен 2016 21:01	2
can anyone give a counterexample if BFS is wrong? kerpoo 11 сен 2016 17:49 I used BFS and getting WA#4 but I don't know why my BFS doesen't get AC! This is my code: #include<bits/stdc++.h> using namespace std; #define X saf[0].first+dir[d][0] #define Y saf[0].second+dir[d][1] #define F first #define S second #define mp make_pair const int M=1002; int dir[8][2]={{0,1},{0,-1},{1,0},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}}; deque<pair<int,int> >saf; pair<int,int> mark[M][M],ans,l[M]; char land[M][M]; int n,m,k; double v; int inland(int x,int y) { if(x<1 \|\| x>n \|\| y<1 \|\| y>m) return false; return true; } void bfs(int h) { for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) mark[i][j].F=mark[i][j].S=0; saf.clear(); saf.push_back(mp(l[h].F,l[h].S)); mark[l[h].F][l[h].S]=mp(1,0); while(saf.size()) { for(int d=0;d<8;d++) if(inland(X,Y)) if(!mark[X][Y].F && !mark[X][Y].S && land[X][Y]=='.') { mark[X][Y]=mark[saf[0].F][saf[0].S]; if(d>3) mark[X][Y].S++; else mark[X][Y].F++; saf.push_back(mp(X,Y)); } saf.pop_front(); } } int main() { cin>>m>>n>>k>>v; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>land[i][j];//scanf("%c",&land[i][j]); for(int i=0;i<=k;i++) scanf("%d%d",&l[i].second,&l[i].first); for(int i=0;i<k;i++) { bfs(i); if(!mark[l[i+1].F][l[i+1].S].F && !mark[l[i+1].F][l[i+1].S].S) { l[i+1]=l[i]; continue; } ans.F+=mark[l[i+1].F][l[i+1].S].F-1; ans.S+=mark[l[i+1].F][l[i+1].S].S; } double x=(double)ans.F+(double)ans.Ssqrt(2.0); printf("%.21f",x/v); return 0; } Edited by author 11.09.2016 17:51* Re: can anyone give a counterexample if BFS is wrong? Jade 11 сен 2016 21:01 BFS is okay, i use BFS in my solution. The thing is, it's not that simple as it usually is, in fact~ Here's an example for you: 5 8 1 1.00 ..... ..... .#... .##.. .###. .##.. .#... ..... 1 1 3 8 If we move down, we do 6 vertical + 1 diagonal + 1 horizontal = 8 jumps with distance 8.41. But, if we move diagonally, we do 4 diagonal jumps right, 2 diagonal jumps left and 1 vertical = 7 jumps, but greater distance (your program says 9.48). So take into account that less "jumps" is not always less distance. If you redo your BFS properly, it should work out. Good luck!
why my modified BFS is wrong	csctcycle	1254. Крепкий орешек	15 дек 2015 17:39	1
why my modified BFS is wrong csctcycle 15 дек 2015 17:39 I define the distance between diagonal block as sqrt(2) and others as 1. Then I use bfs to solve this problem but wa in #4 I don't know the reason.please help
Planar graph	Michael Plusnin (USU)	1254. Крепкий орешек	1 дек 2012 17:42	1
Planar graph Michael Plusnin (USU) 1 дек 2012 17:42 This task can be soved using a linear Frederickson shortest path algo.
A little hint for those, who have TLE and who use Dijkstra's algorithm	Leonid (SLenik) Andrievskiy	1254. Крепкий орешек	3 июл 2011 03:53	1
A little hint for those, who have TLE and who use Dijkstra's algorithm Leonid (SLenik) Andrievskiy 3 июл 2011 03:53 My program was written on C# I had written simple Dijkstra -> TLE #6 [ID = 2902593] I had written Dijkstra over Heap (a.k.a. PriorityQueue) -> TLE #6 [ID = 2902684] I had written Dijkstra over RMQ -> AC (3.296 s) [ID = 3643861] Use RMQ for Dijkstra!
To Admins: please add test	AterLux	1254. Крепкий орешек	3 май 2011 21:21	1
To Admins: please add test AterLux 3 май 2011 21:21 7 5 3 1 ....... .#####. .#...#. .#####. ....... 1 1 3 3 5 3 7 1 one of my AC versions fails with test
WA7	rohit	1254. Крепкий орешек	26 авг 2011 01:41	3
WA7 rohit 12 апр 2011 03:18 What's special in test 7 ? I tried all the tests given here and I get right answer. My algorithm is to use bfs to calculate shortest path from source to each destination. If destination is reachable, source is updated to destination else source remains same. Anything wrong with my method ? Re: WA7 Erop [USU] 2 май 2011 22:47 may be some problems with precision? Re: WA7 Velea Alex 26 авг 2011 01:41 I got the same problem .. i have WA7 .. I used BFs .. O(nmk) with 2 quest .. one for the blocks whose were reached by vertical or orizontal moves ( last move ) and another for those who were reached with diagonal moves (last move counts only again .. ) with this i do not need to use Heap :( but i got a problem .. i triend almoast every test .. and they worked .. but still WA7 .. :( my prog. it's not written so well ... so i will not post it .. if you think that it will help you .. ask for it : ) i will keep in touch with this thread :-S
for C++ coder : <set> is very bad!!!	hoan	1254. Крепкий орешек	2 май 2011 22:44	2
for C++ coder : <set> is very bad!!! hoan 29 ноя 2010 21:47 dont use <set> for dijekstra, use heap. first i use <set> ansd i had TL#7 but when i changed it to heap i Ac in 1.234 s. sorry for my poor english. GOOD LUCK!!! Re: for C++ coder : <set> is very bad!!! SEG 2 май 2011 22:44 my dijksta over <set> gets AC in 3.89
Why wrong answer7? What is this test?	Programmer	1254. Крепкий орешек	28 фев 2009 02:49	1
Why wrong answer7? What is this test? Programmer 28 фев 2009 02:49
Lower TL please	Fyodor Menshikov	1254. Крепкий орешек	19 июн 2009 19:07	3
Lower TL please Fyodor Menshikov 19 фев 2009 00:37 solution ID 1557946: 3 Mar 2007 time 4.75 solution ID 2456185: 19 Feb 2009 time 1.875 source code is identical. It seems that TL for this problem has not been changed since the server upgrade this autumn. I suggest to lower TL from 5s to 2s or rejudge all TLE solutions submitted before server upgrade. +1 OpenGL 19 июн 2009 17:25 +1, but Al.Cash 19 июн 2009 19:07 This problem is far from alone in such situation. The best of all would be to update timelimits for all old problems, but it looks impossible.
Need Help!!! WA4	Lebedev_Nicolay[Ivanovo SPU]	1254. Крепкий орешек	22 янв 2009 23:59	7
Need Help!!! WA4 Lebedev_Nicolay[Ivanovo SPU] 20 янв 2009 00:05 I use simple BFS, but I have wa4; Can anybody help me??? Re: Need Help!!! WA4 Vedernikoff Sergey (HSE: EconomicsForever!) 20 янв 2009 00:29 BFS doesn't work here, since you have edges of different lengths, that's why WA. Think of other algorithm Re: Need Help!!! WA4 OpenGL 20 янв 2009 18:23 I used BFS and got very fast AC Re: Need Help!!! WA4 Lebedev_Nicolay[Ivanovo SPU] 22 янв 2009 22:35 OpenGL, can you check my solution, if yes - give me your mail. void438@mail.ru OpenGL 22 янв 2009 23:58 void438@mail.ru OpenGL 22 янв 2009 23:59 Re: Need Help!!! WA4 Vedernikoff Sergey (HSE: EconomicsForever!) 22 янв 2009 23:54 2 OpenGL: if you use BFS with dequeue - then yes, it's OK. But usual BFS with queue - it's WA
A USEFUL HINT for those TLE authors!!!	198808xc	1254. Крепкий орешек	1 сен 2008 12:31	1
A USEFUL HINT for those TLE authors!!! 198808xc 1 сен 2008 12:31 Many people got TLE on this problem. However, there are ways to avoid TLE. I viewed some topics before, and they told me to use vectors instead of float numbers. I tried, but it doesn't work for my bad programming. After that, I tried to think another way... Many people got TLE, but they only use 7 or 8 sec. Here is a method to make the time derive to half: First, find all avaliable task, and assume the staring point is No.0 then, instead of calculating all the shortest paths, we can calculate this: Shortest from No.1 to No.0 and No.2, (add them up) Shortest from No.3 to No.2 and No.4, (add them up) ...... thus we can easily save half of the time, and My program got AC in 2.8 sec (previously TLE) Sorry for my bad English. Good luck for EVERYONE~
Time Limit Test for You	vetas	1254. Крепкий орешек	29 ноя 2010 21:44	6
Time Limit Test for You vetas 29 май 2008 15:52 75 75 1000 1.23 .########################################################################## ..........................................................................# #########################################################################.# ..........................................................................# .########################################################################## ..........................................................................# #########################################################################.# ..........................................................................# .########################################################################## ..........................................................................# #########################################################################.# ..........................................................................# .########################################################################## ..........................................................................# #########################################################################.# ..........................................................................# .########################################################################## ..........................................................................# #########################################################################.# ..........................................................................# .########################################################################## ..........................................................................# #########################################################################.# ..........................................................................# .########################################################################## ..........................................................................# #########################################################################.# ..........................................................................# .########################################################################## ..........................................................................# #########################################################################.# ..........................................................................# .########################################################################## ..........................................................................# #########################################################################.# ..........................................................................# .########################################################################## ..........................................................................# #########################################################################.# ..........................................................................# .########################################################################## ..........................................................................# #########################################################################.# ..........................................................................# .########################################################################## ..........................................................................# #########################################################################.# ..........................................................................# .########################################################################## ..........................................................................# #########################################################################.# ..........................................................................# .########################################################################## ..........................................................................# #########################################################################.# ..........................................................................# .########################################################################## ..........................................................................# #########################################################################.# ..........................................................................# .########################################################################## ..........................................................................# #########################################################################.# ..........................................................................# .########################################################################## ..........................................................................# #########################################################################.# ..........................................................................# .########################################################################## ..........................................................................# #########################################################################.# ..........................................................................# .########################################################################## ..........................................................................# #########################################################################.. 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 Re: Time Limit Test for You [LG]_#\#@P$T[101]R 13 июл 2008 16:06 ans is 2219446.46 ? Re: Time Limit Test for You vetas 11 ноя 2008 21:02 Yes Re: Time Limit Test for You Leonid (SLenik) Andrievskiy 24 янв 2010 14:38 My program works for about 58 seconds on this test (I'm using Deikstra over Heap) Re: Time Limit Test for You hoan 29 ноя 2010 21:44 tank you very much !!! Re: Time Limit Test for You hoan 29 ноя 2010 21:44 thank you very much !!!
why "WA7"?	vgu	1254. Крепкий орешек	1 май 2009 14:44	3
why "WA7"? vgu 5 фев 2008 17:50 {$A8,B-,C+,D+,E-,F-,G+,H+,I+,J-,K-,L+,M-,N+,O-,P+,Q+,R+,S-,T-,U-,V+,W-,X+,Y+,Z1} program Project5; {$APPTYPE CONSOLE} uses SysUtils; const cn: array [0..1] of extended=(1,1.414213562373095); dx: array [1..8] of integer=(-1,0,1,1,1,0,-1,-1); dy: array [1..8] of integer=(-1,-1,-1,0,1,1,1,0); var a: array [0..76,0..76] of byte; i,j,n,m,k,x,y,x1,y1: integer; v,s,res: extended; ch: char; flag: boolean; procedure wave(x,y,x1,y1,n,m: integer; var res: extended; var flag: boolean); var fl: array [0..76,0..76] of byte; r: array [0..76,0..76] of extended; och: array [1..6000,1..2] of integer; i,j,b,e,xz,yz: integer; begin flag:=false; For i:=1 to n do For j:=1 to m do begin fl[i,j]:=0; r[i,j]:=0; end; b:=1; e:=1; och[b,1]:=x; och[b,2]:=y; fl[y,x]:=1; while b<=e do begin If (och[b,1]=x1) and (och[b,2]=y1) then begin flag:=true; break; end; For i:=1 to 8 do begin xz:=och[b,1]+dx[i]; yz:=och[b,2]+dy[i]; If (a[yz,xz]=0) and (xz>0) and (xz<=m) and (yz>0) and (yz<=n) then begin If fl[yz,xz]=0 then begin inc(e); och[e,1]:=xz; och[e,2]:=yz; r[yz,xz]:=r[och[b,2],och[b,1]]+cn[i mod 2]; fl[yz,xz]:=1; end else If r[yz,xz]>r[och[b,2],och[b,1]]+cn[i mod 2] then r[yz,xz]:=r[och[b,2],och[b,1]]+cn[i mod 2]; end; end; inc(b); end; If flag then res:=r[y1,x1] else res:=0; end; begin readln(m,n,k,v); For i:=1 to n do begin For j:=1 to m do begin read(ch); If ch='#' then a[i,j]:=1 else a[i,j]:=0; end; readln; end; s:=0; readln(x,y); For i:=1 to k do begin readln(x1,y1); wave(x,y,x1,y1,n,m,res,flag); If flag then begin x:=x1; y:=y1; s:=s+res; end; end; write((s/v):0:2); end. Re: why "WA7"? vgu 6 фев 2008 15:43 AC now Re: why "WA7"? sdf 1 май 2009 14:44 I have wa7 too. I used dijkstra. Give me hint, I can't find mistake :(((
Why i got "WA"? help plz	Inside	1254. Крепкий орешек	27 июл 2007 23:33	1
Why i got "WA"? help plz Inside 27 июл 2007 23:33 #include <iostream> #include <vector> #include <queue> #include <cstdio> using namespace std; char A[75][75]; int B[5625][9]; int color[5625]; double d[5625]; int n,m; queue<short> q; const double dva = 1.4142135623730950488016887242097; void BFS(int s) { int i,u; for(i=0;i<nm;i++) { color[i]=0; d[i]=-1.0; } color[s]=1; d[s]=0.0; q.push(s); while (!q.empty()) { u=q.front(); for(i=0;i<8;i++) { if(B[u][i]==-1) break; if(color[B[u][i]]==0) { color[B[u][i]]=1; if(B[u][i]==(u-1) \|\| B[u][i]==(u+1) \|\| B[u][i]==(u-n) \|\| B[u][i]==(u+n)) d[B[u][i]]=d[u]+1.0; else d[B[u][i]]=d[u]+dva; q.push(B[u][i]); } } q.pop(); color[u]=2; } } int main() { int k,i,j,x,y,s,f,u,z,c; double dist=0.0,v; cin>>n>>m>>k>>v; for(i=0;i<m;i++) for(j=0;j<n;j++) cin>>A[i][j]; for(i=0;i<nm;i++) { j=0;u=i; if((u+n)<(nm) && A[(u+n)/n][(u+n)%n]!='#') {B[i][j]=(u+n);j++;} if((u-n)>-1 && A[(u-n)/n][(u-n)%n]!='#') {B[i][j]=(u-n);j++;} if((u+1)%n!=0 && A[(u+1)/n][(u+1)%n]!='#') {B[i][j]=(u+1);j++;} if(u%n!=0 && A[(u-1)/n][(u-1)%n]!='#') {B[i][j]=(u-1);j++;} if((u-n-1)>-1 && (u-n)%n!=0 && A[(u-n-1)/n][(u-n-1)%n]!='#'){B[i][j]=(u-n-1);j++;} if((u-n+1)>-1 && (u-n+1)%n!=0 && A[(u-n+1)/n][(u-n+1)%n]!='#'){B[i][j]=(u-n+1);j++;} if((u+n-1)<(nm) && (u+n)%n!=0 && A[(u+n-1)/n][(u+n-1)%n]!='#'){B[i][j]=(u+n-1);j++;} if((u+n+1)<(nm) && (u+n+1)%n!=0 && A[(u+n+1)/n][(u+n+1)%n]!='#'){B[i][j]=(u+n+1);j++;} B[i][j]=-1; } cin>>y>>x; s=(x-1)n+y-1; for(i=0;i<k;i++) { BFS(s); cin>>y>>x; f=(x-1)*n+y-1; if(d[f]==-1) continue; dist+=d[f]; s=f; } printf("%.2lf\n",dist/v); return 0; }
Страница 1
Strange WA #2	M@STeR.SoBG	1254. Крепкий орешек	22 окт 2011 16:55	7
Strange WA #2 M@STeR.SoBG 25 июл 2007 05:43 What can be in this test? What answer for this test? 5 1 1 0.02 .#... 1 1 5 1 Is answer "0.00"??? "0.00" is correct (+) Rafail Ahmadisheff 9 авг 2007 01:15 M@STeR.SoBG писал(a) 25 июля 2007 05:43 Is answer "0.00"??? Yes. It is "0.00". If he can't reach some bomb he moves to the next one. What if none of the bombs can be reached? If this is the case, you may assume, that agent's mission is complete - he can do nothing, so he does nothing and it takes him no time to do it! I got WA in #2 too TlaughE 19 ноя 2007 09:45 Is that #2? Re: I got WA in #2 too KALO 28 окт 2010 00:14 I can't get through test#2 please help. Re: I got WA in #2 too Ibragim Atadjanov (Tashkent U of IT) 12 ноя 2010 08:15 I also had that problem(wa2). But when I made a test I understood my mistake and got ac. I've used dijkstra and in main method I did like this for(int i = 0; i< k - 1; i ++){ dijkstra(i); ...... } and this was wrong example imagine I cannot reach to th 3rd boomb.So my walk will be like this 0 ->1 ->2 ->3(unreachable) 3->4 ..... instead, it must be like this 0 ->1 ->2 ->3(unreachable) 2->4 ..... I dont know your problem but mine was like above [stupid(:] test 5 5 5 1 ..... .###. .#.#. .###. ..... 1 1 5 1 3 3 5 5 1 5 1 3 ans 14 If it wont help, you can post me ur code(to email) Edited by author 12.11.2010 08:20 Re: I got WA in #2 too KALO 15 ноя 2010 00:06 Thank you! Re: I got WA in #2 too Edric Mao 22 окт 2011 16:55 Thanks
How to speed up?	Fyodor Menshikov	1254. Крепкий орешек	3 мар 2007 23:09	1
How to speed up? Fyodor Menshikov 3 мар 2007 23:09 I have solved this problem is Java, by now it is the only solution in this not fast language. :-) My solution was rather advanced, real arithmetics only on output, but it used almost all given time 4.75 / 5.00 s. Then I saw statistics of this problem. There are solutions that work much less than 1s. Is it advantage of fast C++ compiler, is it advantage of hand-written data structures (I used standard PriorityQueue) or is algorithm used much more advanced than mine? Could anyone explain optimizations of really (<1s) fast solution?
That I should do if John can't reach last bomb	Dembel {AESC USU}	1254. Крепкий орешек	26 дек 2006 15:23	2
That I should do if John can't reach last bomb Dembel {AESC USU} 6 окт 2006 12:55 Edited by author 26.12.2006 16:16 What output... Dembel {AESC USU} 26 дек 2006 15:23 input 3 3 3 1 .#. ### .#. 1 1 1 3 3 1 3 3 output 0.0 this output is correct, isn't it?

Страницы: 2 1 Предыдущая

Вид форума: плоский | древовидный | классический
Сортировка веток: всплывающая | фиксированная

Обсуждение задачи 1254. Крепкий орешек