#include <iostream>
#include <stdio.h>
#include <string>
#include <vector>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <math.h>
using namespace std;
int R, C;
int grid[250][250];
int bannedNumber;
int x, y;
int jigglyPuff;
int L;
bool boundaryCheck(int x, int y)
{
if(x <0 || y <0 || x>= R || y >= C)
{
return false;
}
return true;
}
int bfs()
{
if(grid[0][0] == 1)
{
return -1;
}
bool visited[200][200] = {false};
int dest[200][200] = {0};
bool found = false;
visited[0][0] = true;
dest[0][0] = 0;
queue<pair<int,int>> qu;
qu.push({0,0});
pair<int,int> pf;
int tempX, tempY;
while(qu.size() != 0)
{
pf = qu.front();
qu.pop();
tempX = pf.first-1;
tempY = pf.second;
if(boundaryCheck(tempX, tempY) == true
&& visited[tempX][tempY] == false
&& grid[tempX][tempY] == 0)
{
visited[tempX][tempY] = true;
dest[tempX][tempY] = dest[pf.first][pf.second] + 1;
if(tempX == (R-1) && tempY == (C-1))
{
found = true;
break;
}
qu.push({tempX, tempY});
}
tempX = pf.first;
tempY = pf.second + 1;
if(boundaryCheck(tempX, tempY) == true
&& visited[tempX][tempY] == false
&& grid[tempX][tempY] == 0)
{
visited[tempX][tempY] = true;
dest[tempX][tempY] = dest[pf.first][pf.second] + 1;
if(tempX == (R-1) && tempY == (C-1))
{
found = true;
break;
}
qu.push({tempX, tempY});
}
tempX = pf.first+1;
tempY = pf.second;
if(boundaryCheck(tempX, tempY) == true
&& visited[tempX][tempY] == false
&& grid[tempX][tempY] == 0)
{
visited[tempX][tempY] = true;
dest[tempX][tempY] = dest[pf.first][pf.second] + 1;
if(tempX == (R-1) && tempY == (C-1))
{
found = true;
break;
}
qu.push({tempX, tempY});
}
tempX = pf.first;
tempY = pf.second - 1;
if(boundaryCheck(tempX, tempY) == true
&& visited[tempX][tempY] == false
&& grid[tempX][tempY] == 0)
{
visited[tempX][tempY] = true;
dest[tempX][tempY] = dest[pf.first][pf.second] + 1;
if(tempX == (R-1) && tempY == (C-1))
{
found = true;
break;
}
qu.push({tempX, tempY});
}
}
if(found == true)
{
return dest[R-1][C-1];
}
return -1;
}
int main() {
std::ios::sync_with_stdio(false);
while(cin>>R>>C)
{
if(R == 0 && C == 0)
{
break;
}
for(int i = 0; i < R; i++)
{
for(int j = 0; j < C; j++)
{
grid[i][j] = 0;
}
}
cin>>bannedNumber;
for(int i = 0; i < bannedNumber; i++)
{
cin>>x>>y;
x--;
y--;
grid[x][y] = 1;
}
cin>>jigglyPuff;
for(int i = 0; i < jigglyPuff; i++)
{
cin>>x>>y>>L;
x--;
y--;
grid[x][y] = 1;
for(int j= y+1; j <= (y+L); j++)
{
if(boundaryCheck(x, j) == false)
{
break;
}
if(((x-x)*(x-x)+ (j-y)*(j-y)) <= (L*L))
{
grid[x][j] = 1;
}
//grid[x][j] = 1;
}
for(int j = x-1; j>= (x-L); j--)
{
if(boundaryCheck(j, y) == false)
{
break;
}
if(((x-j)*(x-j)+ (y-y)*(y-y)) <= (L*L))
{
grid[j][y] = 1;
}
//grid[j][y] = 1;
}
for(int j = y -1; j >= (y - L); j--)
{
if(boundaryCheck(x, j) == false)
{
break;
}
if(((x-x)*(x-x)+ (y-j)*(y-j)) <= (L*L))
{
grid[x][j] = 1;
}
//grid[x][j] = 1;
}
for(int j = x+1; j <= (x+L); j++)
{
if(boundaryCheck(j, y) == false)
{
break;
}
if(((x-j)*(x-j)+ (y-y)*(y-y)) <= (L*L))
{
grid[j][y] = 1;
}
//grid[j][y] = 1;
}
}
int res = bfs();
if(res == -1)
{
cout<<"Impossible.\n";
}
else
{
cout<<res<<"\n";
}
}
return 0;
}
Write, Run & Share C++ code online using OneCompiler's C++ online compiler for free. It's one of the robust, feature-rich online compilers for C++ language, running on the latest version 17. Getting started with the OneCompiler's C++ compiler is simple and pretty fast. The editor shows sample boilerplate code when you choose language as C++ and start coding!
OneCompiler's C++ online compiler supports stdin and users can give inputs to programs using the STDIN textbox under the I/O tab. Following is a sample program which takes name as input and print your name with hello.
#include <iostream>
#include <string>
using namespace std;
int main()
{
string name;
cout << "Enter name:";
getline (cin, name);
cout << "Hello " << name;
return 0;
}
C++ is a widely used middle-level programming language.
When ever you want to perform a set of operations based on a condition If-Else is used.
if(conditional-expression) {
//code
}
else {
//code
}
You can also use if-else for nested Ifs and If-Else-If ladder when multiple conditions are to be performed on a single variable.
Switch is an alternative to If-Else-If ladder.
switch(conditional-expression){
case value1:
// code
break; // optional
case value2:
// code
break; // optional
......
default:
code to be executed when all the above cases are not matched;
}
For loop is used to iterate a set of statements based on a condition.
for(Initialization; Condition; Increment/decrement){
//code
}
While is also used to iterate a set of statements based on a condition. Usually while is preferred when number of iterations are not known in advance.
while (condition) {
// code
}
Do-while is also used to iterate a set of statements based on a condition. It is mostly used when you need to execute the statements atleast once.
do {
// code
} while (condition);
Function is a sub-routine which contains set of statements. Usually functions are written when multiple calls are required to same set of statements which increases re-usuability and modularity. Function gets run only when it is called.
return_type function_name(parameters);
function_name (parameters)
return_type function_name(parameters) {
// code
}