Page 2 of 3

Posted: Fri Jun 04, 2004 9:22 pm
by shuniu
My solution in Java got AC in 9.953s, talking about cutting it close!!!
I think these kind of long input questions are really discriminating to the Java users. Java programs are about 5-10x slower (or even more) than the C, C++, Pascal programs. Even a System.out.println("") takes 0.006s, eg it can never reach the 0.000 status.

Posted: Tue May 08, 2007 3:59 pm
by nymo
Isn't this a plain BFS? I am getting WAs. Can someone provide some cases? and I guess there is always a path to the destination...

Posted: Tue May 08, 2007 5:41 pm
by DP
Yes, it is a plain BFS. Make input yourself. Then post it for correctness.

Acc now.

Posted: Tue May 08, 2007 7:51 pm
by nymo
Hi, I am new in C++. I tried to implement the code using STL queue and find that I need to clear the queue before trying next inputs... :oops: Anyway, 've learnt a new thing :D and its ACC now, thanks.

Re: 10653 - Bombs! NO they are Mines!!

Posted: Sun Apr 12, 2009 8:02 pm
by JohnTortugo
I've coded it using STL Queue for DFS and it pass easy...

Also I think there isn't a test with no route, anyway my program prints 0x3f3f3f3f in decimal 8)

Good luck, John.

Re: 10653 - Bombs! NO they are Mines!!

Posted: Sun Jun 12, 2011 4:52 pm
by Chocolate
Hi all, isn't this only a BFS problem? I don't know why my code keep TLE. I even use C I/O but it still TLE.

here is the code:

Code: Select all

#include<iostream>
#include<cstdio>
#include<queue>
#define INF (1<<29)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define FORN(i,a) FOR(i,0,a)
using namespace std;

typedef struct {
	int x,y,steps;
} Point;

int mat [1010][1010];
int m,n;
int nb,ncol,br,bc;
int sx,sy,ex,ey;

int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};

inline int bfs(int x, int y){
	Point st;
	st.x=x;
	st.y=y;
	st.steps=0;
	queue<Point> q;
	q.push(st);
	while(!q.empty()){
		Point top = q.front(); q.pop();
		if (top.x == ex && top.y == ey) return top.steps;
		mat[top.x][top.y]=1;
		FORN(i,3){
			int nx = top.x+dx[i];
			int ny = top.y+dy[i];
			if (nx >= 0 && nx < m && ny >=0 && ny < n && mat[nx][ny] != 1){
				Point next; next.x = nx; next.y = ny; next.steps = top.steps+1;
				q.push(next);
			}
		}
	}
	return -1; //shouldn't happen
}

int main(){

	while(/*cin>>m>>n*/scanf("%d%d",&m,&n) == 2){
		if(m==0&&n==0) break;
		FORN(i,m-1) FORN(j,n-1) mat[i][j] = 0;
		//cin>>nb;
		scanf("%d",&nb);
		FORN(i,nb-1){
			//cin>>br>>ncol;
			scanf("%d%d",&br,&ncol);
			FORN(j,ncol-1){
				//cin>>bc;
				scanf("%d",&bc);
				mat[br][bc]=1;
			}
		}
		//cin>>sx>>sy>>ex>>ey;
		scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
		//cout << bfs(sx,sy) << endl;
		printf("%d\n",bfs(sx,sy));
	}
	
	return 0;
}
I appreciate any help. :D

Re: 10653 - Bombs! NO they are Mines!!

Posted: Tue Sep 11, 2012 3:59 pm
by pranon
AC.

Re: 10653 - Bombs! NO they are Mines!!

Posted: Tue Sep 11, 2012 8:51 pm
by brianfry713
I looked at your first version. You're not marking each node as visited as you enqueue it, so you're going to be revisiting nodes and have multiple copies of a node in the queue, which will cause TLE. Try this input:

Code: Select all

1000 1000
0
0 0
999 999
0 0
My AC code prints 1998 in .1 sec on my machine, yours seg faults.
http://en.wikipedia.org/wiki/Breadth-first_search

Re: 10653 - Bombs! NO they are Mines!!

Posted: Fri Feb 08, 2013 12:01 pm
by Mukit Chowdhury
Accepted ....

Re: 10653 - Bombs! NO they are Mines!!

Posted: Wed Jul 31, 2013 1:52 pm
by Faithkeeper_Rangwan
I tried many different inputs, but still WA

Code: Select all

#include <cstring>
#include <queue>
#include <utility>
#include <iostream>
#include <sstream>
#include <string>

int mp[1000][1000];
int main()
{
    int c,r,b;

    int bomr,bomc;

    int startr,startc;
    int endr,endc;


    std::cin>>r>>c;
    while(r|c)
    {
        memset(mp,-1,sizeof(int)*1000000);
        std::queue<std::pair<int,int> > q;
        std::cin>>b;
        while ((b--)>=0)
        {
            std::string txt;
            std::getline(std::cin,txt);
            std::stringstream ss(txt);

            ss>>bomr;
            while(ss.good())
            {
                ss>>bomc;
                mp[bomr][bomc] = -2;
            }
        }
        std::cin>>startr>>startc;
        std::cin>>endr>>endc;
        mp[startr][startc] = 0;
        q.push(std::make_pair(startr,startc));
        int number = 0;
        while(!q.empty())
        {
            int x = q.front().first,y = q.front().second;
            if((x+1<r)&&(mp[x+1][y]> -2)&&((mp[x+1][y]<0)||(mp[x+1][y]>mp[x][y]+1))) {mp[x+1][y] = mp[x][y] + 1; q.push(std::make_pair(x+1,y)); }
            if((x-1>=0)&&(mp[x-1][y]> -2)&&((mp[x-1][y]<0)||(mp[x-1][y]>mp[x][y]+1))) {mp[x-1][y] = mp[x][y] + 1; q.push(std::make_pair(x-1,y)); }

            if((y+1<c)&&(mp[x][y+1]> -2)&&((mp[x][y+1]<0)||(mp[x][y+1]>mp[x][y]+1))) {mp[x][y+1] = mp[x][y] + 1; q.push(std::make_pair(x,y+1)); }
            if((y-1>=0)&&(mp[x][y-1]> -2)&&((mp[x][y-1]<0)||(mp[x][y-1]>mp[x][y]+1))) {mp[x][y-1] = mp[x][y] + 1; q.push(std::make_pair(x,y-1)); }
            q.pop();
        }
        std::cout<<mp[endr][endc]<<std::endl;
        std::cin>>r>>c;
    }
    return 0;
}
Ps. it computes within 0.372 sec

Re: 10653 - Bombs! NO they are Mines!!

Posted: Thu Aug 01, 2013 12:39 am
by brianfry713
For each of the rows, you'd have one line of input. These lines start with the row number, followed by the number of bombs in that row. Then you'd have the column locations of that many bombs in that row.

You don't need to use getline, you can just use cin. You're not reading the number of bombs in each row.

Try this input:

Code: Select all

3 3
3
0 1 2
1 1 2
2 1 0
0 0
2 2
0 0
Output should be 4

Re: 10653 - Bombs! NO they are Mines!!

Posted: Wed Nov 13, 2013 6:06 pm
by Devil_Bird
Can anyone give some testcase this is my code that gets WA!!!!

Code: Select all

AC

Re: 10653 - Bombs! NO they are Mines!!

Posted: Thu Nov 14, 2013 12:45 am
by brianfry713
change line 71 to:
if(i==0 || j==0 || i==r+1 ||j==c+1 )

Re: 10653 - Bombs! NO they are Mines!!

Posted: Thu Nov 14, 2013 3:46 pm
by Devil_Bird
thanks briyanfry you're awesome!!! :D

Re: 10653 - Bombs! NO they are Mines!!

Posted: Fri Jun 20, 2014 11:38 pm
by Mrsuit
Tried several input and i'm getting WA. Please help!

Code: Select all

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;


public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader b = new BufferedReader(new InputStreamReader(System.in));
		String line;
		StringBuilder sb= new StringBuilder();
		while((line=b.readLine())!=null && !line.equals("0 0")){
			String[] nums = line.split(" ");

			int r = Integer.parseInt(nums[0]);
			int c = Integer.parseInt(nums[1]);

			int[][] matrix = new int[r][c];

			int loop = Integer.parseInt(b.readLine());



			for(int i = 0; i < loop; i++){
				nums = b.readLine().split(" ");
				int fila = Integer.parseInt(nums[0]);
				for (int j = 2; j < Integer.parseInt(nums[1]) + 2; j++){
					matrix[fila][Integer.parseInt(nums[j])]=1;
				}
			}

			nums=b.readLine().split(" ");
			int in1=Integer.parseInt(nums[0]); int in2=Integer.parseInt(nums[1]);
			nums=b.readLine().split(" ");
			int fn1=Integer.parseInt(nums[0]); int fn2=Integer.parseInt(nums[1]);

			////Algoritmo

			Queue<Integer> q = new LinkedList<Integer>(); 
			//matrix[in1][in2]=0;
			q.add(in1);q.add(in2);
			//Queue<Integer> q1=new LinkedList<Integer>();

				while (!q.isEmpty() ){
					int x=q.poll(); int y=q.poll();
					if (x+1<r && matrix[x+1][y]==0){
						matrix[x+1][y]= matrix[x][y]+1;
						q.add(x+1);q.add(y);
					}
					if (x-1>0 && matrix[x-1][y]==0){
						matrix[x-1][y]= matrix[x][y]+1;
						q.add(x-1);q.add(y);
					}
					if (y+1<c && matrix[x][y+1]==0){
						matrix[x][y+1]= matrix[x][y]+1;
						q.add(x);q.add(y+1);
					}
					if (y-1>0 && matrix[x][y-1]==0){
						matrix[x][y-1]= matrix[x][y]+1;
						q.add(x);q.add(y-1);
					}						
					if (matrix[fn1][fn2]!=0){
						break;
					}
				}
				
			sb.append(matrix[fn1][fn2]+"\n");

		}
		System.out.print(sb);
	}
}


Edit: Already found the mistake and got AC.