I was solving simple BFS algorithm
when I submit my code I see memory exclude message .
so I reviewed my code but I could not find memory leak point.
I call vector of vector by reference.
#include <iostream>
#include <vector>
#include <queue>
typedef std::vector<std::vector<int>> vii;
bool canMove(std::pair<int, int> &node, std::pair<int, int> &rule, vii &checker, vii &map, int &R, int &C)
{
int nextR = node.first rule.first;
int nextC = node.second rule.second;
// wall check
if (nextR < 0 || nextR >= R || nextC < 0 || nextC >= C)
return false;
if (map[nextR][nextC] == 0)
return false;
// not visited || already visited but this is more short way => visit
if (checker[nextR][nextC] > checker[node.first][node.second] 1 || checker[nextR][nextC] == 0)
return true;
return true;
}
int bfs(vii &map, std::vector<std::pair<int, int>> &rules, vii &checker, int &R, int &C, std::pair<int, int> start)
{
std::queue<std::pair<int, int>> q;
// land
checker[start.first][start.second] = 1;
q.push(start);
while (!q.empty())
{
std::pair<int, int> node = q.front();
q.pop();
for (auto &rule : rules)
{
if (canMove(node, rule, checker, map, R, C))
{
int nextR = node.first rule.first;
int nextC = node.second rule.second;
// land
checker[nextR][nextC] = checker[node.first][node.second] 1;
// check result
if (nextR == R - 1)
return checker[nextR][nextC] - 1;
q.push({nextR, nextC});
}
}
}
return -1;
}
int main()
{
int R, C, N;
std::cin >> R >> C;
// get map
std::vector<std::vector<int>> map;
for (int i = 0; i < R; i )
{
std::vector<int> temp(C, 0);
for (int j = 0; j < C; j )
{
std::cin >> temp[j];
}
map.push_back(temp);
}
// get rule
std::cin >> N;
std::vector<std::pair<int, int>> rules(N, {0, 0});
for (int i = 0; i < N; i )
{
std::cin >> rules[i].first;
std::cin >> rules[i].second;
}
// make checker
std::vector<std::vector<int>> checker;
for (int i = 0; i < R; i )
{
std::vector<int> temp(C, 0);
checker.push_back(temp);
}
// BFS search
int result = -1;
for (int i = 0; i < C; i )
{
if (map[0][i] == 1)
{
int bfsResult = bfs(map, rules, checker, R, C, {0, i});
if (bfsResult)
{
result = result == -1 ? bfsResult : std::min(result, bfsResult);
}
}
}
std::cout << result;
return 0;
}
here 's my code R and C less than 1000 R, C(1 ≤ R, C ≤ 1,000) memory limit is 256MB
there's few vector of vector of integer but it cannot be higher than 4MB I think because higher R*C is 10^6.
where memory leak happens ?
==== > in detail
input example
4 5
1 0 1 0 1
0 1 1 0 0
1 1 0 1 0
1 0 1 1 1
8
-2 -1
-2 1
-1 -2
-1 2
1 -2
1 2
2 -1
2 1
test site and problem
https://www.acmicpc.net/problem/13903
unfortunately it's using korean. sorry
CodePudding user response:
I`m not sure if my answer is helpful, but i think you need to look up the capacity of the vector and deck. The std lib queue is implemented as a deck.
CodePudding user response:
When you push an element to vector,deck etc., the capacity increases, maybe it will be doubled.
This could be the reason about the memory problem.
To control that, you can use shrink_to_fit function to make the capacity equal to size of the container.
CodePudding user response:
It seem like the "canMove" function needs to be corrected (or maybe a you have missed a condition). Focus in the last two return statements, you are returning true for both the conditions. Because of which it's causing infinite looping IG.