11624 - Fire!

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

Moderator: Board moderators

jddantes
Learning poster
Posts: 73
Joined: Sat Mar 08, 2014 8:55 am

Re: 11624 - Fire!

Post by jddantes » Thu Jul 24, 2014 10:18 am

Why is mine TLE? Is it just the input processing or do I choose a different algorithm altogether (like the one mentioned, calculating the distances to the edges)?

Code: Select all

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

class mypair{
public:
    int cost, vertex;
    bool edge;
    mypair(int COST, int VERTEX, bool EDGE){
        cost = COST;
        vertex = VERTEX;
        edge = EDGE;
    }

    bool operator< (const mypair &x ) const {
        return cost > x.cost;
    }
};

int main(){

    int cases;
    scanf("%d", &cases);

    for(int e= 0; e<cases; e++){

        int r, c;
        scanf("%d %d", &r, &c);
        char grid[r][c];
        for(int i =0; i<r; i++){
            for(int j = 0; j<c; j++){
                scanf(" %c", &grid[i][j]);
            }
        }

        vector< vector<mypair> > adjList(r*c);
        vector<int> fireIndex;

        int startIndex;
        bool jIsEdge = false;
        for(int i = 0; i<r; i++){
            for(int j = 0; j<c; j++){
                int INDEX = i*c + j;
                if(grid[i][j] == '#')
                    continue;
                if(grid[i][j] == '.'){
                    // TOP
                    if(i-1 >=0){
                        int I = i-1;
                        int J = j;
                        int VERTEX = I*c+J;
                        bool EDGE = false;
                        if(I==0 || I == r-1 || J == 0 || J == c-1)
                            EDGE = true;
                        if(grid[I][J] == '.' || grid[I][J] == 'J'){
                            adjList[INDEX].push_back(mypair(1, VERTEX, EDGE));
                        }
                    }
                    // BOTTOM

                    if(i+1<r){
                        int I = i+1;
                        int J = j;
                        int VERTEX = I*c+J;
                        bool EDGE = false;
                        if(I==0 || I == r-1 || J == 0 || J == c-1)
                            EDGE = true;
                        if(grid[I][J] == '.' || grid[I][J] == 'J'){
                            adjList[INDEX].push_back(mypair(1, VERTEX, EDGE));
                        }
                    }

                    // LEFT
                    if(j-1>=0){
                        int I = i;
                        int J = j-1;
                        int VERTEX = I*c+J;
                        bool EDGE = false;
                        if(I==0 || I == r-1 || J == 0 || J == c-1)
                            EDGE = true;
                        if(grid[I][J] == '.' || grid[I][J] == 'J'){
                            adjList[INDEX].push_back(mypair(1, VERTEX, EDGE));
                        }
                    }

                    // RIGHT
                    if(j+1<c){
                        int I = i;
                        int J = j+1;
                        int VERTEX = I*c+J;
                        bool EDGE = false;
                        if(I==0 || I == r-1 || J == 0 || J == c-1)
                            EDGE = true;
                        if(grid[I][J] == '.' || grid[I][J] == 'J'){
                            adjList[INDEX].push_back(mypair(1, VERTEX, EDGE));
                        }
                    }



                } else if (grid[i][j] == 'J'){
                    startIndex = i*c+j;
                    if(i==0||j==0||i==r-1||j==c-1)
                        jIsEdge = true;
                    // TOP
                    if(i-1 >=0){
                        int I = i-1;
                        int J = j;
                        int VERTEX = I*c+J;
                        bool EDGE = false;
                        if(I==0 || I == r-1 || J == 0 || J == c-1)
                            EDGE = true;
                        if(grid[I][J] == '.' || grid[I][J] == 'J'){
                            adjList[INDEX].push_back(mypair(1, VERTEX, EDGE));
                        }
                    }
                    // BOTTOM

                    if(i+1<r){
                        int I = i+1;
                        int J = j;
                        int VERTEX = I*c+J;
                        bool EDGE = false;
                        if(I==0 || I == r-1 || J == 0 || J == c-1)
                            EDGE = true;
                        if(grid[I][J] == '.' || grid[I][J] == 'J'){
                            adjList[INDEX].push_back(mypair(1, VERTEX, EDGE));
                        }
                    }

                    // LEFT
                    if(j-1>=0){
                        int I = i;
                        int J = j-1;
                        int VERTEX = I*c+J;
                        bool EDGE = false;
                        if(I==0 || I == r-1 || J == 0 || J == c-1)
                            EDGE = true;
                        if(grid[I][J] == '.' || grid[I][J] == 'J'){
                            adjList[INDEX].push_back(mypair(1, VERTEX, EDGE));
                        }
                    }

                    // RIGHT
                    if(j+1<c){
                        int I = i;
                        int J = j+1;
                        int VERTEX = I*c+J;
                        bool EDGE = false;
                        if(I==0 || I == r-1 || J == 0 || J == c-1)
                            EDGE = true;
                        if(grid[I][J] == '.' || grid[I][J] == 'J'){
                            adjList[INDEX].push_back(mypair(1, VERTEX, EDGE));
                        }
                    }
                } else if (grid[i][j] == 'F'){

                    fireIndex.push_back(INDEX);

                    // TOP
                    if(i-1 >=0){
                        int I = i-1;
                        int J = j;
                        int VERTEX = I*c+J;
                        bool EDGE = false;
                        if(I==0 || I == r-1 || J == 0 || J == c-1)
                            EDGE = true;
                        if(grid[I][J] == '.' || grid[I][J] == 'J'){
                            adjList[INDEX].push_back(mypair(1, VERTEX, EDGE));
                        }
                    }
                    // BOTTOM

                    if(i+1<r){
                        int I = i+1;
                        int J = j;
                        int VERTEX = I*c+J;
                        bool EDGE = false;
                        if(I==0 || I == r-1 || J == 0 || J == c-1)
                            EDGE = true;
                        if(grid[I][J] == '.' || grid[I][J] == 'J'){
                            adjList[INDEX].push_back(mypair(1, VERTEX, EDGE));
                        }
                    }

                    // LEFT
                    if(j-1>=0){
                        int I = i;
                        int J = j-1;
                        int VERTEX = I*c+J;
                        bool EDGE = false;
                        if(I==0 || I == r-1 || J == 0 || J == c-1)
                            EDGE = true;
                        if(grid[I][J] == '.' || grid[I][J] == 'J'){
                            adjList[INDEX].push_back(mypair(1, VERTEX, EDGE));
                        }
                    }

                    // RIGHT
                    if(j+1<c){
                        int I = i;
                        int J = j+1;
                        int VERTEX = I*c+J;
                        bool EDGE = false;
                        if(I==0 || I == r-1 || J == 0 || J == c-1)
                            EDGE = true;
                        if(grid[I][J] == '.' || grid[I][J] == 'J'){
                            adjList[INDEX].push_back(mypair(1, VERTEX, EDGE));
                        }
                    }
                }
            }
        }

        if(jIsEdge){
            printf("1\n");
        } else {
            bool found = false;

            vector<bool> visited(r*c, false);
            vector<bool> firevisited(r*c, false);
            priority_queue<mypair> que;
            queue<mypair> fque;

            que.push(mypair(0, startIndex, false));
            for(int i = 0; i<fireIndex.size(); i++){
                fque.push(mypair(0, fireIndex[i], false));
            }
            while(!que.empty() && !found ){
                mypair currentNode = que.top();
                que.pop();
/*
                printf("Visited: ");
                for(int i = 0; i<r*c; i++){
                    if(visited[i])
                        printf("%d ", i);
                }
                printf("Burned: ");
                for(int i =0; i<r*c; i++){
                    if(firevisited[i])
                        printf("%d ", i);
                }
                printf("\n");*/

                // If visited or burned skip
                if(visited[currentNode.vertex] || firevisited[currentNode.vertex])
                    continue;

                visited[currentNode.vertex] = true;

                if(currentNode.edge){
                    printf("%d\n", currentNode.cost+1);
                    found = true;
                    break;
                }

                // Walk to adj Nodes
                for(int i = 0; i<adjList[currentNode.vertex].size(); i++){
                    mypair adjNode = adjList[currentNode.vertex][i];

                    if(visited[adjNode.vertex] || firevisited[adjNode.vertex])
                        continue;

                    que.push(mypair(currentNode.cost+1, adjNode.vertex, adjNode.edge));
                }

                // Spread fire
                int fquesize = fque.size();
                for(int x=0; x<fquesize; x++){
                    mypair fireNode = fque.front();
                    fque.pop();

                    // Burn adj nodes

                    for(int i = 0; i<adjList[fireNode.vertex].size(); i++){
                        mypair adjNode = adjList[fireNode.vertex][i];
                        // If burned, skip
                        if(firevisited[adjNode.vertex])
                            continue;

                        firevisited[adjNode.vertex] = true;
                        fque.push(adjNode);
                    }


                }
            }

            if(!found){
                printf("IMPOSSIBLE\n");
            }

        }


    }

    return 0;
}

lbv
Experienced poster
Posts: 128
Joined: Tue Nov 29, 2011 8:40 am

Re: 11624 - Fire!

Post by lbv » Thu Jul 24, 2014 11:32 am

jddantes wrote:Why is mine TLE?
The general idea behind your approach may be okay, but there's a number of things that make it difficult for an implementation like that to get AC.
  • Your program uses a significant amount of memory unnecesarily. The grid you read from the input, for example, already contains all the information you need in order to know where you can get to from any particular cell, but you duplicate this information in the form of (cost, vertex, isEdge) tuples which slow down the program, because of memory cache invalidation and given that the grids can be relatively large (10^6 bytes).
  • A similar thing happens with the 2 vectors you use to store information about whether each cell has been visited (by fire or not). All of that could be stored and updated in the original grid, saving a significant amount of memory, and increasing memory locality and the speed of your program.
  • A priority queue is not necessary. Notice that the core algorithm behind your approach is a BFS, which can be implemented with a simple queue, which has reduced insertion/query complexity compared to a priority queue.
  • On top of all this, this problem has a relatively low time limit (just 1 sec).
My suggestion would be to start by simplifying your code as much as possible; make sure it uses as little memory as possible. As I mentioned, you could use the original char grid to keep track of all the information that your current program keeps in vectors and vectors of vectors. You can also get away with just one standard queue instead of one queue and one priority queue for the BFS.

Another simple change that can have a significant effect is to avoid reading each character individually. An alternative to this:

Code: Select all

		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++) {
				scanf(" %c", &grid[i][j]);
			}
		}
is this:

Code: Select all

		for (int i = 0; i < r; i++)
			scanf("%s", grid[i]);
Nonetheless, I think by far the most important thing would be to simplify the rest of the code.

Also try these cases:

Input

Code: Select all

2
10 10
..........
..........
.....F....
..........
.FF.......
..........
.......F..
.....J....
..........
..........
9 6
.F####
##F.#.
.....#
.....#
.#....
.#.#..
##...#
..#.J#
.#F..#
Output

Code: Select all

3
2

jddantes
Learning poster
Posts: 73
Joined: Sat Mar 08, 2014 8:55 am

Re: 11624 - Fire!

Post by jddantes » Thu Jul 24, 2014 12:10 pm

Thanks for the reply, I used another way to work with the grid and accommodated your test cases. Got AC :)

jddantes
Learning poster
Posts: 73
Joined: Sat Mar 08, 2014 8:55 am

Re: 11624 - Fire!

Post by jddantes » Thu Jul 24, 2014 3:55 pm

I've solved this with one BFS, but I wanted to try it with two, but got TLE. What else can be optimized here?

Code: Select all

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

#define INF 2<<20

using namespace std;

class mypair{
public:
	int i, j, cost;
	mypair(int I, int J, int COST){
		i = I;
		j = J;
		cost = COST;
	}
	bool operator<(const mypair & x ) const{
		return x.cost > cost;
	}
};

int main(){

	int cases;
	scanf("%d", &cases);
	for(int e = 0; e<cases; e++){
		int r, c;
		scanf("%d %d", &r, &c);

		char grid[r+2][c+2];

		for(int j = 0; j<c+2; j++){
			grid[0][j] = '#';
			grid[r+1][j] = '#';
		}
		for(int i = 0; i<r+2; i++){
			grid[i][0] = '#';
			grid[i][c+1] = '#';
		}

		mypair Joe(0,0,0);
		queue<mypair> fq;

		for(int i = 1; i<=r; i++){
			for(int j = 1; j<=c; j++){
				scanf(" %c", &grid[i][j]);
				if(grid[i][j] == 'J'){
					Joe = mypair(i, j, 0);
				}
				if(grid[i][j] == 'F'){
					fq.push(mypair(i,j,0));
				}
			}
		}

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

		vector< vector<int> > joeAns (r+2, vector<int>(c+2, INF));
		vector< vector<int> > fireAns (r+2, vector<int>(c+2, INF));

		vector< vector<bool> > visited (r+2, vector<bool>(c+2, false));
		vector< vector<bool> > firevisited(r+2, vector<bool>(c+2, false));

		queue<mypair> que;
		
		que.push(Joe);

		while(!que.empty()){
			mypair currentNode = que.front();
			que.pop();

			if(visited[currentNode.i][currentNode.j])
				continue;
			
			visited[currentNode.i][currentNode.j] = true;
			joeAns[currentNode.i][currentNode.j] = currentNode.cost;
			// printf("Got %d %d\n", currentNode.i, currentNode.j);

			for(int y = 0; y<4; y++){
				mypair adjNode = mypair(currentNode.i+dy[y], currentNode.j+dx[y], currentNode.cost+1);
				if(grid[adjNode.i][adjNode.j] == '#')
					continue;
				if(visited[adjNode.i][adjNode.j])
					continue;

				que.push(mypair(adjNode.i, adjNode.j, currentNode.cost+1));
				// printf("Walking to %d %d\n", adjNode.i, adjNode.j);
			}
		}

		// for(int i = 1; i<r+1; i++){
		// 	for(int j = 1; j<c+1; j++){
		// 		if(joeAns[i][j] == INF){
		// 			printf("-1");
		// 		}else
		// 		printf("%d ", joeAns[i][j]);
		// 	}
		// 	printf("\n");
		// }


		while(!fq.empty()){	
				mypair currentNode = fq.front();
				fq.pop();

				if(firevisited[currentNode.i][currentNode.j])
					continue;

				firevisited[currentNode.i][currentNode.j] = true;

				if(fireAns[currentNode.i][currentNode.j] < currentNode.cost)
					continue;

				fireAns[currentNode.i][currentNode.j] = currentNode.cost;

				for(int y = 0; y<4; y++){
					mypair adjNode = mypair(currentNode.i + dy[y], currentNode.j + dx[y], currentNode.cost + 1);

					if(grid[adjNode.i][adjNode.j]=='#')
						continue;
					if(firevisited[adjNode.i][adjNode.j])
						continue;

					fq.push(mypair(adjNode.i, adjNode.j, currentNode.cost+1));
				}

			}

		// for(int i = 1; i<r+1; i++){
		// 	for(int j = 1; j<c+1; j++){
		// 		if(joeAns[i][j]==INF){
		// 			printf("- ");
		// 		} else {
		// 			printf("%d ", joeAns[i][j]);
		// 		}
		// 	}
		// 	puts("");
		// }
		// printf("Fire\n");
		// for(int i = 1; i<r+1; i++){
		// 	for(int j = 1; j<c+1; j++){
		// 		if(fireAns[i][j]==INF){
		// 			printf("- ");
		// 		} else {
		// 			printf("%d ", fireAns[i][j]);
		// 		}
		// 	}
		// 				puts("");

		// }

		int minCost = INF;

		for(int i = 1; i<r+1; i++){

			if(joeAns[i][1] < fireAns[i][1]){
				if(joeAns[i][1] < minCost){
					minCost = joeAns[i][1];
				}
			}

			if(joeAns[i][c] < fireAns[i][c]){
				if(joeAns[i][c] < minCost){
					minCost = joeAns[i][c];
				}
			}
		}

		for(int j = 1; j<c+1; j++){
			if(joeAns[1][j] < fireAns[1][j]){
				if(joeAns[1][j] < minCost){
					minCost = joeAns[1][j];
				}
			}

			if(joeAns[r][j] < fireAns[r][j]){
				if(joeAns[r][j] < minCost){
					minCost = joeAns[r][j];
				}
			}
		}

		if(minCost == INF){
			printf("IMPOSSIBLE\n");
		} else {
			printf("%d\n", minCost + 1);
		}




	}

	return 0;
}

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

Re: 11624 - Fire!

Post by brianfry713 » Thu Jul 24, 2014 10:06 pm

brianfry713 wrote:Here's how I solved this problem.
I first run BFS to calculate the minimum time it takes a square to catch on fire. I insert every initial F square into a queue and each of those takes time 0 to catch on fire.
I then run BFS starting from Joe. Joe can move if he can reach that square before it catches on fire. Calculate the earliest time Joe can make it out of the maze.
I use two different 1000 by 1000 int arrays to keep track of the minimum times it takes a square to catch on fire and the minimum time it takes Joe to reach a square.

Try to modify your code to match my algorithm.
I only put the locations on the queue, not the cost.
Check input and AC output for thousands of problems on uDebug!

jddantes
Learning poster
Posts: 73
Joined: Sat Mar 08, 2014 8:55 am

Re: 11624 - Fire!

Post by jddantes » Thu Jul 31, 2014 5:06 am

Isn't cost used to keep track of the time it takes to reach a square from a source?

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

Re: 11624 - Fire!

Post by brianfry713 » Thu Jul 31, 2014 10:35 pm

Yes but read my algorithm description.
I put the cost into an int array which should be faster than pushing it onto the queue, I also used fixed size arrays rather than vectors which should also speed things up.
Also my algorithm is different from yours.
Check input and AC output for thousands of problems on uDebug!

re_60
New poster
Posts: 2
Joined: Sun Jan 25, 2015 10:44 pm
Location: Bangladesh

Re: 11624 - Fire!

Post by re_60 » Thu Feb 05, 2015 3:18 pm

can anybody help plz :( already got 10 wrong ans...cant find the bug... all the testcases in this forum works well :(

Code: Select all

code removed after AC  :) 
keep calm and smile on

crazytim
New poster
Posts: 3
Joined: Tue Feb 17, 2015 10:37 am

Re: 11624 - Fire!

Post by crazytim » Tue Feb 17, 2015 10:59 am

I think my approach to this problem can run in time limit. I let all the fires move one step before Joe moves until he escapes the maze or he is surrounded by fires.
But actually, I got TLE many times and don't know why. Can someone help me to point where is wrong?

Code: Select all

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

const int N = 1002;

struct pos
{
	int x, y;	
};

int n, m;
char maze[N][N];
queue<pos> person;
queue<pos> fire;
int dir[4][2] = { {1, 0}, {-1, 0}, {0, -1}, {0, 1} };
bool escape, dead;


inline bool inMaze(int x, int y)
{
	return x >= 1 && x <= n && y >= 1 && y <= m;
}

void expand()
{
	int num = fire.size();
	int nx, ny;
	int tx, ty;
	
	while(num --)
	{
		nx = fire.front().x;
		ny = fire.front().y;
		fire.pop();
		
		for(int d = 0; d < 4; d ++)
		{
			tx = nx + dir[d][0];
			ty = ny + dir[d][1];
			
			if(inMaze(tx, ty) && maze[tx][ty] == '.')
			{
				maze[tx][ty] = 'F';
				fire.push((pos){tx, ty});
			}
		}
	}
} 

void move()
{
	int num = person.size();
	int nx, ny;
	int tx, ty;
	
	if(num == 0)
	{
		dead = true;
		return;
	}
	
	while(num --)
	{
		nx = person.front().x;
		ny = person.front().y;
		person.pop();
		
					
		for(int d = 0; d < 4; d ++)
		{
			tx = nx + dir[d][0];
			ty = ny + dir[d][1];
			
			if(!inMaze(tx, ty))
			{
				escape = true;
				return;
			}
			
			if(maze[tx][ty] == '.')
			{
				maze[nx][ny] = 'J';
				person.push((pos){tx, ty});
			}
		}
	}
}

int main()
{
	int testcases;
	
	scanf("%d", &testcases);
	while(testcases --)
	{
		scanf("%d %d", &n, &m);
		
		for(int i = 1; i <= n; i ++)
			scanf("%s", maze[i] + 1);
		
		while(person.size() > 0) person.pop();
		while(fire.size() > 0) fire.pop();
		
		for(int i = 1; i <= n; i ++)
		{	
			for(int j = 1; j <= m; j ++)
			{	
				if(maze[i][j] == 'J')
					person.push((pos){i, j});
				else if(maze[i][j] == 'F')
					fire.push((pos){i, j});
			}
		}
		
		int times = 0;
		escape = false, dead = false;
		
		while(true)
		{
			times ++;
			
			expand();
			move();
			
			if(escape == true || dead == true)
				break;
		}
		
		if(escape == true)
			printf("%d\n", times);
		if(dead == true)
			printf("IMPOSSIBLE\n");
		
		
	}

	return 0;
}

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

Re: 11624 - Fire!

Post by brianfry713 » Tue Feb 17, 2015 11:32 pm

brianfry713 wrote:Here's how I solved this problem.
I first run BFS to calculate the minimum time it takes a square to catch on fire. I insert every initial F square into a queue and each of those takes time 0 to catch on fire.
I then run BFS starting from Joe. Joe can move if he can reach that square before it catches on fire. Calculate the earliest time Joe can make it out of the maze.
I use two different 1000 by 1000 int arrays to keep track of the minimum times it takes a square to catch on fire and the minimum time it takes Joe to reach a square.

Try to modify your code to match my algorithm.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 116 (11600-11699)”