10653 - Bombs! NO they are Mines!!

All about problems in Volume 106. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

shuniu
New poster
Posts: 34
Joined: Thu Oct 16, 2003 6:15 pm

Post by shuniu » Fri Jun 04, 2004 9:22 pm

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.

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

Post by nymo » Tue May 08, 2007 3:59 pm

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...
regards,
nymo

DP
Learning poster
Posts: 62
Joined: Sun Aug 13, 2006 9:15 am
Location: Bangladesh
Contact:

Post by DP » Tue May 08, 2007 5:41 pm

Yes, it is a plain BFS. Make input yourself. Then post it for correctness.

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

Acc now.

Post by nymo » Tue May 08, 2007 7:51 pm

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.
regards,
nymo

JohnTortugo
New poster
Posts: 18
Joined: Sun Jul 20, 2008 7:05 pm

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

Post by JohnTortugo » Sun Apr 12, 2009 8:02 pm

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.

Chocolate
New poster
Posts: 3
Joined: Sat Jun 11, 2011 3:17 pm

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

Post by Chocolate » Sun Jun 12, 2011 4:52 pm

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

pranon
New poster
Posts: 14
Joined: Mon Jul 23, 2012 2:39 pm

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

Post by pranon » Tue Sep 11, 2012 3:59 pm

AC.
Last edited by pranon on Tue Sep 11, 2012 9:00 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

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

Post by brianfry713 » Tue Sep 11, 2012 8:51 pm

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
Check input and AC output for thousands of problems on uDebug!

Mukit Chowdhury
Learning poster
Posts: 98
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

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

Post by Mukit Chowdhury » Fri Feb 08, 2013 12:01 pm

Accepted ....

Faithkeeper_Rangwan
New poster
Posts: 12
Joined: Sun Jul 07, 2013 7:32 pm

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

Post by Faithkeeper_Rangwan » Wed Jul 31, 2013 1:52 pm

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

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

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

Post by brianfry713 » Thu Aug 01, 2013 12:39 am

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
Check input and AC output for thousands of problems on uDebug!

Devil_Bird
New poster
Posts: 10
Joined: Sun Mar 17, 2013 12:02 am

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

Post by Devil_Bird » Wed Nov 13, 2013 6:06 pm

Can anyone give some testcase this is my code that gets WA!!!!

Code: Select all

AC
Last edited by Devil_Bird on Thu Nov 14, 2013 3:48 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

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

Post by brianfry713 » Thu Nov 14, 2013 12:45 am

change line 71 to:
if(i==0 || j==0 || i==r+1 ||j==c+1 )
Check input and AC output for thousands of problems on uDebug!

Devil_Bird
New poster
Posts: 10
Joined: Sun Mar 17, 2013 12:02 am

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

Post by Devil_Bird » Thu Nov 14, 2013 3:46 pm

thanks briyanfry you're awesome!!! :D

Mrsuit
New poster
Posts: 14
Joined: Mon May 05, 2014 8:41 pm

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

Post by Mrsuit » Fri Jun 20, 2014 11:38 pm

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.

Post Reply

Return to “Volume 106 (10600-10699)”