Here's a problem that I tried solving:
Lakshagraha was a house built of lacquer, made by the Kauravas to kill the Pandavas. The Kauravas wanted to burn the house down when the Pandavas were asleep at night. But poor Kauravas – once again they underestimated their cousins. Having been warned of the nefarious plan, the Pandavas had had an underground set of passages built for escape.
The underground rooms and passages were in the form of a n*m grid where every cell is either free or blocked by a pillar. The Pandavas start at a free cell and they need to reach a destination cell(which can be free or blocked).
The following are the allowed valid moves:
Move from an empty cell to another adjacent empty cell. (Cells sharing a common side are considered adjacent).
If an adjacent cell is blocked, then set the edge of the blocked cell on fire.
If two or more (distinct) edges of a blocked cell are set on fire, then the blocking pillar burns down and clears the cell. After the fire, the cell becomes empty.
Initially no edge of any blocked cell is set on fire. Help the Pandavas find whether it is possible to reach the destination (target cell), because they are the good guys.
Input: The first line contains T, the number of test cases. The description of T Test cases follow. The first line of each test case consists of 2 space separated integers n and m, denoting the dimensions of the grid (n x m grid). Each of the following n lines contain m characters each, where the jth character of the ith line denotes the state of the cell located at the jth column of the ith row of the grid. Each cell can either be blocked (denoted by ‘*’), or free (denoted by ‘.’). The next line of each test case consists of 4 space separated integers sx, sy, ex, ey, where (sx, sy) denotes the cell where you are initially located at, and (ex, ey) denotes the destination cell (1 based indices).
Output: For each test case, output a single line containing
YES
orNO
, denoting whether it is possible to reach the destination cell from the given starting cell by making valid moves as described above.Constraints:
- \$T ≤ 20\$
- \$1 ≤ n\$
- \$m ≤ 500\$
- \$1 ≤ sx\$, \$ex ≤ n\$
- \$1 ≤ sy\$, \$ey ≤ m\$
- The starting cell is always empty.
Sample Input
3 2 3 .*. ... 1 1 1 3 3 3 ..* ..* .*. 2 1 3 3 2 3 .*. **. 2 3 1 2
Sample Output
YES YES NO
Time Limit: 2 sec
Memory Limit: 256 MB
Initially, I used a backtracking approach to solve the problem. Obviously, that was slow and resulted in TLE. Later, I was told that a simple BFS would do. Hence, I just did a simple BFS, starting at the specified point. Whenever I encounter a pillar, I increase its count and see if its more than 1 (The pillar has been visited twice). If so, I push it into the queue and continue the BFS. Still, the code results in TLE. I really don't know how I can optimize this code more!
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
class data
{
public:
int count;
int x;
int y;
int flag;
char value;
}ob;
int main() {
// your code goes here
int test;
scanf("%d",&test);
int n,m;
char temp;
while(test--)
{
scanf("%d%d",&n,&m);
//printf("%d %d",n,m);
data ar[n][m];
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
scanf(" %c",&temp);
ob.count=0;
ob.x = i;
ob.y = j;
ob.value = temp;
ar[i][j] = ob;
}
}
int sx,sy,ex,ey;
scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
vector<data> v;
sx-=1;
sy-=1;
ex-=1;
ey-=1;
v.push_back(ar[sx][sy]);
int x,y;
while(true)
{
if(v.size()==0)
{
printf("NO\n");
break;
}
else
{
ob = v[0];
v.erase(v.begin());
x = ob.x;
y = ob.y;
//cout<<"Current : "<<x<< " "<<y<<endl;
ar[x][y].flag=1;
if(x+1<n)
{
if(ar[x+1][y].flag!=1)
{
if(ar[x+1][y].value == '.')
{
if(x+1 == ex && y == ey)
{
printf("YES\n");
break;
}
else
v.push_back(ar[x+1][y]);
}
else
{
ar[x+1][y].count+=1;
if(ar[x+1][y].count>1)
{
if(x+1 == ex && y == ey)
{
printf("YES\n");
break;
}
else
v.push_back(ar[x+1][y]);
}
}
}
}
if(x-1>=0)
{
if(ar[x-1][y].flag!=1)
{
if(ar[x-1][y].value == '.')
{
if(x-1 == ex && y == ey)
{
printf("YES\n");
break;
}
else
v.push_back(ar[x-1][y]);
}
else
{
ar[x-1][y].count+=1;
if(ar[x-1][y].count>1)
{
if(x-1 == ex && y == ey)
{
printf("YES\n");
break;
}
else
v.push_back(ar[x-1][y]);
}
}
}
}
if(y+1<m)
{
if(ar[x][y+1].flag!=1)
{
if(ar[x][y+1].value == '.')
{
if(x == ex && y+1 == ey)
{
printf("YES\n");
break;
}
else
v.push_back(ar[x][y+1]);
}
else
{
ar[x][y+1].count+=1;
if(ar[x][y+1].count>1)
{
if(x == ex && y+1 == ey)
{
printf("YES\n");
break;
}
else
v.push_back(ar[x][y+1]);
}
}
}
}
if(y-1>=0)
{
if(ar[x][y-1].flag!=1)
{
if(ar[x][y-1].value == '.')
{
if(x == ex && y-1 == ey)
{
printf("YES\n");
break;
}
else
v.push_back(ar[x][y-1]);
}
else
{
ar[x][y-1].count+=1;
if(ar[x][y-1].count>1)
{
if(x == ex && y-1 == ey)
{
printf("YES\n");
break;
}
else
v.push_back(ar[x][y-1]);
}
}
}
}
}
}
}
return 0;
}
begin(v)
tov.begin()
. A text search on Sutter for "Nonmember begin and end" explains why: The basic rationale is that nonmemberbegin
/end
are more extensible. \$\endgroup\$