vis not changing

[RexLee]

This is the uva problem: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=513

Here is my code (c++):

#include <iostream>#define maxn 100 + 10char grid[maxn][maxn];int convert[maxn][maxn];int vis[maxn][maxn];int m, n;void dfs(int x, int y){     if (x < 0 || x >= n || y < 0 || y >= m) return;     if (!vis[x][y] || convert[x][y]) return;     vis[x][y] = 1;     dfs(x - 1, y - 1);     dfs(x - 1, y);     dfs(x - 1, y + 1);     dfs(x, y - 1);     dfs(x, y + 1);     dfs(x + 1, y - 1);     dfs(x + 1, y);     dfs(x + 1, y + 1);}int main(){    int count;    while(std::cin >> m >> n)    {        if (m == 0)            break;        count = 0;        for (int i = 0; i < m; ++i)            for (int j = 0; j < n; ++j)            {                vis[i][j] = 0;                std::cin >> grid[i][j];                if (grid[i][j] == '#')                    convert[i][j] = 0;                else if (grid[i][j] == '@')                    convert[i][j] = 1;            }        for (int i = 0; i < m; ++i)            for (int j = 0; j < n; ++j)            {                if (!vis[i][j] && convert[i][j])                {                    ++count;                     dfs(i, j);                }            }        std::cout << count << std::endl;    }    system("pause");    return 0;}

But it isn't giving me the right answer.

I think it is because vis[][] wasn't changing.

What is wrong here?

[Ciccioo]

this

     if (!vis[x][y] || convert[x][y]) return;

is always true, so it always returns

it should be

     if (vis[x][y] || convert[x][y]) return;

which means "if the place HAS already been visited, skip it"

[RexLee]

The answer is still wrong though.

So what else if wrong?

[Ciccioo]

The answer is still wrong though.

So what else if wrong?

another thing is actually in the same row, i didn't notice it before

     if (vis[x][y] || convert[x][y]) return;

should be

     if (vis[x][y] || !convert[x][y]) return;

"if it HAS already been visited or there is NO oil, skip this"

 

edit

     if (x < 0 || x >= n || y < 0 || y >= m) return;

should be

     if (x < 0 || x >= m || y < 0 || y >= n) return;

you made a little bit of confusion there

[RexLee]

Oh, thank you.

I didn't write the code all in one day so i guess i got confused.

[RexLee]

By the way if I did this by bfs.

What would be the difference?

I can't really tell them apart.

Except I read one was stack and the other was queue?

[Ciccioo]

By the way if I did this by bfs.

What would be the difference?

I can't really tell them apart.

Except I read one was stack and the other was queue?

mmm the conceptual difference between dfs and bfs is not so clear in an example like this imo

 

it would just change the order in which the nodes are visited

take this case

@@@@@@@@@

3x3 grid, every node is a pocket

 

your implementation of dfs would visit the nodes like this

1 2 35 4 86 7 9

doing 9 recursions (it went deep), one node visited per ricursion

 

a bfs that evaluates nodes in the same order as your dfs would explore the grid like this

1 2 53 4 67 8 9

but it would only take 3 wide scans, it kinda expands radially from (0, 0)

0 | |- ┘ |----┘

ASCII drawing like a boss

 

dfs is better suited for a recursive implementation

bfs is better suited for a iterative impementation

 

so

 

dfs is easier to impement, or it takes less code at least, but is less memory efficient because it will quickly fill up the stack

bfs is longer to implement without using libraries for the queue, but is much more memory efficient and scalable

 

your problem had a limit of 100*100 = 10000 nodes, so it could lead to 10000 recursions in the worst case scenario

a C++ implementation running on a modern computer shouldn't cause stack overflow for 10k recursions, but it's getting a bit dangerous

100k recursions would be out of question, for example, it would probably just not work

edit: it crashes after about 65k recursions on my high end system running win 8.1

edit: seems to handle 260k recursions on an ubuntu 13.10 based distro