| ENG RUS | Timus Online Judge |
Discussion of Problem 1254. Die Hard👑TIMOFEY👑 WA7 // Problem 1254. Die Hard 26 Jun 2023 19:02 you don't know how to write bfs, try watching videos for beginners 👑TIMOFEY👑 WA6 // Problem 1254. Die Hard 26 Jun 2023 18:40 precision Abid29 wa 9 // Problem 1254. Die Hard 24 Apr 2021 00:07 use sqrt(2.00) instead of 1.41421356 kerpoo can anyone give a counterexample if BFS is wrong? [1] // Problem 1254. Die Hard 11 Sep 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.S*sqrt(2.0); printf("%.21f",x/v); return 0; } Edited by author 11.09.2016 17:51 Jade Re: can anyone give a counterexample if BFS is wrong? // Problem 1254. Die Hard 11 Sep 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! csctcycle why my modified BFS is wrong // Problem 1254. Die Hard 15 Dec 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 Michael Plusnin (USU) Planar graph // Problem 1254. Die Hard 1 Dec 2012 17:42 This task can be soved using a linear Frederickson shortest path algo. hello It's a good problem ! [3] // Problem 1254. Die Hard 25 Jun 2004 19:03 svr Re: It's a good problem ! [2] // Problem 1254. Die Hard 4 Feb 2007 11:27 One of solvable by Dijksta with heap. But interesting how to speed up. Idea: use struct (int,int*sqrt(2)) instead of double for distances with compair: (h1,h2*sqrt(2))<(q1,q2*sqrt(2))~ (h1-q1)^2<2*(h2-q2)^2 in int type. Alias (Alexander Prudaev) Re: It's a good problem ! // Problem 1254. Die Hard 24 Mar 2007 21:02 i have used other method, and i have best AC 0.265 sec 220 kb IgorKoval(from Pskov) Re: It's a good problem ! // Problem 1254. Die Hard 22 Dec 2011 03:53 svr wrote 4 February 2007 11:27 One of solvable by Dijksta with heap. But interesting how to speed up. Idea: use struct (int,int*sqrt(2)) instead of double for distances with compair: (h1,h2*sqrt(2))<(q1,q2*sqrt(2))~ (h1-q1)^2<2*(h2-q2)^2 in int type. I have read you massage and after wrote as you said. I got TLE. I changed <<<struct harT{long k1, k2;};>>> on <<<double>>> and get AC. Conclusion: It's not good idea or I don't undestand you. =) Edited by author 22.12.2011 03:53 Edited by author 22.12.2011 03:54 M@STeR.SoBG Strange WA #2 [6] // Problem 1254. Die Hard 25 Jul 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"??? Rafail Ahmadisheff "0.00" is correct (+) [5] // Problem 1254. Die Hard 9 Aug 2007 01:15 M@STeR.SoBG wrote 25 July 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!TlaughE I got WA in #2 too [4] // Problem 1254. Die Hard 19 Nov 2007 09:45 Is that #2? KALO Re: I got WA in #2 too [3] // Problem 1254. Die Hard 28 Oct 2010 00:14 I can't get through test#2 please help. Ibragim Atadjanov (Tashkent U of IT) Re: I got WA in #2 too [2] // Problem 1254. Die Hard 12 Nov 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 KALO Re: I got WA in #2 too // Problem 1254. Die Hard 15 Nov 2010 00:06 Thank you! Edric Mao Re: I got WA in #2 too // Problem 1254. Die Hard 22 Oct 2011 16:55 Thanks rohit WA7 [2] // Problem 1254. Die Hard 12 Apr 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 ? Erop [USU] Re: WA7 [1] // Problem 1254. Die Hard 2 May 2011 22:47 may be some problems with precision? Velea Alex Re: WA7 // Problem 1254. Die Hard 26 Aug 2011 01:41 I got the same problem .. i have WA7 .. I used BFs .. O(n*m*k) 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 Leonid (SLenik) Andrievskiy A little hint for those, who have TLE and who use Dijkstra's algorithm // Problem 1254. Die Hard 3 Jul 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! AterLux To Admins: please add test // Problem 1254. Die Hard 3 May 2011 21:21 7 5 3 1 ....... .#####. .#...#. .#####. ....... 1 1 3 3 5 3 7 1 one of my AC versions fails with test hoan for C++ coder : <set> is very bad!!! [1] // Problem 1254. Die Hard 29 Nov 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!!! SEG Re: for C++ coder : <set> is very bad!!! // Problem 1254. Die Hard 2 May 2011 22:44 my dijksta over <set> gets AC in 3.89 vetas Time Limit Test for You [5] // Problem 1254. Die Hard 29 May 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 [LG]_#\#@P$T[101]R Re: Time Limit Test for You [2] // Problem 1254. Die Hard 13 Jul 2008 16:06 ans is 2219446.46 ? vetas Re: Time Limit Test for You [1] // Problem 1254. Die Hard 11 Nov 2008 21:02 Yes Leonid (SLenik) Andrievskiy Re: Time Limit Test for You // Problem 1254. Die Hard 24 Jan 2010 14:38 My program works for about 58 seconds on this test (I'm using Deikstra over Heap) hoan Re: Time Limit Test for You // Problem 1254. Die Hard 29 Nov 2010 21:44 tank you very much !!! hoan Re: Time Limit Test for You // Problem 1254. Die Hard 29 Nov 2010 21:44 thank you very much !!! Fyodor Menshikov Lower TL please [2] // Problem 1254. Die Hard 19 Feb 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. OpenGL +1 [1] // Problem 1254. Die Hard 19 Jun 2009 17:25 Al.Cash +1, but // Problem 1254. Die Hard 19 Jun 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. vgu why "WA7"? [2] // Problem 1254. Die Hard 5 Feb 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. vgu Re: why "WA7"? [1] // Problem 1254. Die Hard 6 Feb 2008 15:43 AC now sdf Re: why "WA7"? // Problem 1254. Die Hard 1 May 2009 14:44 I have wa7 too. I used dijkstra. Give me hint, I can't find mistake :((( Programmer Why wrong answer7? What is this test? // Problem 1254. Die Hard 28 Feb 2009 02:49 Lebedev_Nicolay[Ivanovo SPU] Need Help!!! WA4 [6] // Problem 1254. Die Hard 20 Jan 2009 00:05 I use simple BFS, but I have wa4; Can anybody help me??? Vedernikoff Sergey (HSE: EconomicsForever!) Re: Need Help!!! WA4 [5] // Problem 1254. Die Hard 20 Jan 2009 00:29 BFS doesn't work here, since you have edges of different lengths, that's why WA. Think of other algorithm OpenGL Re: Need Help!!! WA4 [4] // Problem 1254. Die Hard 20 Jan 2009 18:23 I used BFS and got very fast AC Lebedev_Nicolay[Ivanovo SPU] Re: Need Help!!! WA4 [2] // Problem 1254. Die Hard 22 Jan 2009 22:35 OpenGL, can you check my solution, if yes - give me your mail. OpenGL void438@mail.ru // Problem 1254. Die Hard 22 Jan 2009 23:58 OpenGL void438@mail.ru // Problem 1254. Die Hard 22 Jan 2009 23:59 Vedernikoff Sergey (HSE: EconomicsForever!) Re: Need Help!!! WA4 // Problem 1254. Die Hard 22 Jan 2009 23:54 2 OpenGL: if you use BFS with dequeue - then yes, it's OK. But usual BFS with queue - it's WA 198808xc A USEFUL HINT for those TLE authors!!! // Problem 1254. Die Hard 1 Sep 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~ uuuuuuu Could you explain the sample to me please ? [1] // Problem 1254. Die Hard 5 Apr 2003 20:29 I understand the problem like that : J - john's position B - bomb The first way is : J 1 0 0 # # 2 0 B 3 0 0 So the time needed is 3 * 1.23 = 3.69 The second : 0 0 0 B # # 2 0 J 1 0 0 Here the time 2 * 1.23 = 2.64 Total = 2.46 + 3.69 = 6.29 The third : 0 0 0 J # # 0 1 0 0 0 B time = 1.23 total = >>>> 7.52 <<<<< ????!!!!! the answer in the sample isn't even a multiple of v ??!!! WOuld You be so kind and explain it to me ?? vetas Re: Could you explain the sample to me please ? // Problem 1254. Die Hard 4 Jun 2008 13:53 >>So the time needed is >>3 * 1.23 = 3.69 if move diagonal distance is sqrt(2) (2+2*(sqrt(2)))/1.23=3.9255 Inside Why i got "WA"? help plz // Problem 1254. Die Hard 27 Jul 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<n*m;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<n*m;i++) { j=0;u=i; if((u+n)<(n*m) && 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)<(n*m) && (u+n)%n!=0 && A[(u+n-1)/n][(u+n-1)%n]!='#'){B[i][j]=(u+n-1);j++;} if((u+n+1)<(n*m) && (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; }
|