i am solving this question on leetcode:
my strategy to solve this is:
- run dfs for each cell index (x,y) on each dfs call check
- if cell is a destination cell accordingly set the flags
- if both flags are true then add this cell to "ans" vector else carry on with the next dfs
my code:
#include <iostream>
using namespace std;
#include <vector>
class Solution {
public:
void psUtil(vector<vector<int> >&mat, int x, int y, int m, int n, int &isP, int &isA, vector<vector<int> >&vis, vector<vector<int> >&ans)
{
//check dstinations
if(x == 0 || y == 0)
{
//cout << "P true" << " x and y are " << x << y << endl;
isP = 1;
}
if(x == m-1 || y == n-1)
{
//cout << "A true" << " x and y are " << x << y << endl;
isA = 1;
}
vector<int> cell(2);
cell[0] = x;
cell[1] = y;
// check both dst rched
if(isA && isP)
{
// append to ans
//cout << "ans = " << cell[0] << " " << cell[1] << endl;
ans.push_back(cell);
return;
}
// mark vis
vis.push_back(cell);
int X[] = {-1, 0, 1, 0};
int Y[] = {0, 1, 0, -1};
int x1, y1;
// check feasible neighbours
for(int i = 0; i < 4; ++i)
{
x1 = x + X[i];
y1 = y + Y[i];
if(x1 < 0 || y1 < 0 || x1 >= m || y1 >= n) continue;
//cout << "if(mat.at(x1).at(y1) <= mat.at(x).at(y))" << endl;
if(mat.at(x1).at(y1) <= mat.at(x).at(y))
{
vector<vector<int> > :: iterator it;
vector<int> cell1(2);
cell1[0] = x1;
cell1[1] = y1;
it = find(vis.begin(), vis.end(), cell1);
if(it != vis.end())
continue;
psUtil(mat, x1, y1, m, n, isP, isA, vis, ans);
if(isA && isP) return;
}
}
}
vector<vector<int> > pacificAtlantic(vector<vector<int> >& matrix)
{
// find dimensions
int m = matrix.size(); // rows
int n = matrix[0].size(); // cols
vector<vector<int> >ans;
// flags if rched destinations
int isP, isA;
isP = isA = 0;
// iterate for all indices
for(int x = 0; x < m; ++x)
{
for(int y = 0; y < n; ++y)
{
// visited nested vector
vector<vector<int> >vis;
psUtil(matrix, x, y, m, n, isP, isA, vis, ans);
isP = isA = 0;
}
}
return ans;
}
};
/*
int main()
{
vector<vector<int> > mat{ {1,2,2,3,5},
{3,2,3,4,4},
{2,4,5,3,1},
{6,7,1,4,5},
{5,1,1,2,4} };
Solution ob;
vector<vector<int> > ans;
ans = ob.pacificAtlantic(mat);
for(int i = 0; i < ans.size(); ++i)
{
for(int j = 0; j < ans[0].size(); ++j)
{
cout << ans[i][j] << " ";
}
cout << endl;
}
return 0;
}
*/
for the given sample input my output is:
0 4
1 4
0 3
2 4
4 0
4 2
4 0
and the correct output is suppose to be:
[[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
where is this program going wrong?
Aucun commentaire:
Enregistrer un commentaire