11624 - Fire!

[jddantes]

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]

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]

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

[jddantes]

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]

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.

[jddantes]

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

[brianfry713]

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.

[re_60]

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  :) 

[crazytim]

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]

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.