10653 - Bombs! NO they are Mines!!

[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.

[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...

[DP]

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

[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... Anyway, 've learnt a new thing and its ACC now, thanks.

[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

Good luck, John.

[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.

[pranon]

AC.

[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

[Mukit Chowdhury]

Accepted ....

[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

[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

[Devil_Bird]

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

Code: Select all

AC

[brianfry713]

change line 71 to:
if(i==0 || j==0 || i==r+1 ||j==c+1 )

[Devil_Bird]

thanks briyanfry you're awesome!!!

[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.