Wierd problem

Debugging Help
#1

Problem Info

buckets http://www.usaco.org/index.php?page=viewproblem2&cpid=939

My Work

#include <bits/stdc++.h>
#include
#include
#include
#include <unordered_set>
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include <unordered_map>
#include
#include
#include
#include

using namespace std;
using ll = long long;

using vi = vector;
#define pb push_back
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

using pi = pair<int, int>;
#define f first
#define s second
#define mp make_pair

void setIO(string name = “”) {
cin.tie(0)->sync_with_stdio(0); // see /general/fast-io
if (sz(name)) {
//freopen((name + “.in”).c_str(), “r”, stdin); // see /general/io
//freopen((name + “.out”).c_str(), “w”, stdout);
}

}

template istream& operator>>(istream& is, vector& vec) {
for (auto& v : vec) is >> v;
return is;
}

const int MAXN = 1e5 + 10;
const int INF = 1e9 + 1;
bool is_int(double f) { return floor(f) == f; }

void max_self(int& a, int b)
{
a = max(a, b);
}

int gcd(ll a, ll b)
{
if (b == 0)
return a;
return gcd(b, a % b);

}
long long lcm(ll a, ll b)
{
return (a / gcd(a, b)) * b;
}
pair<int, int> directions[4] = { {1,0},{0,1},{-1,0},{0,-1} };
bool valide(int i, int j)
{
return i >= 0 && i < 10 && j >= 0 && j < 10;
}
bool visited[10][10];
int minimal(int i, int j, const char firm[10][10], int step)
{
if (firm[j][i] == ‘R’)
return INT_MAX;

if (firm[i][j] == 'L')
{
    return step;
}
int ans = INT_MAX;
visited[i][j] = true;

for (auto D : directions)
{
    int new_i = i + D.first, new_j = j + D.second;
    if (valide(new_i,new_j ))
    {
        if (!visited[new_i][new_j])
        {
            
                ans = min(ans, minimal(new_i, new_j, firm, step + 1));
        }
    }
}

visited[i][j] = false;



return ans;

}

int main() {
std::ios::sync_with_stdio(false);
cin.tie(0);

 //setIO("buckets");

char firm[10][10];
int fire_i, fire_j;
for (int i = 0; i < 10; i++)
    for (int j = 0; j < 10; j++)
    {
        cin >> firm[i][j];
        visited[i][j] = false;
        if (firm[i][j] == 'B')
        {
            fire_i = i;
            fire_j = j;
        }
    }

cout << minimal(fire_i, fire_j, firm, 0) << endl;





return 0;

}
Add commented code here

Add explanation of code here
as you can see i have tried a simple DFS code but for some raison that i can't put my hand on i don't find why it's never stop or give the right answer.
## What I've Tried
Let us know what you've tried. Have you tried downloading the test data? Have you tried writing a brute force script? etc.

## Question
Include a specific question if you have one.

## Checklist
See [How to ask for help on a problem](https://forum.usaco.guide/t/how-to-ask-for-help-on-a-problem/338/2) for more information.
- Include a link to the problem
- Format your post (especially code blocks)
- Include what you've tried so far
- Add comments to your code
- Read the [debugging module](https://usaco.guide/general/debugging-general)
#2

So… have you tried downloading the test data?

Also, please fix the formatting of your code.

#3

DFS does not work for this problem. DFS is guaranteed to find a path, but not the shortest (hence the name depth first). Either try BFS or a more case-by-case approach. Notice there is only one rock, so you don’t need a super general solution.

#4

umm why are there so many #include. You can just use #include<bits/stdc++.h> to include all library. Note that this won’t work for some other contests tho.

#5

yes , it’s just another way to do full brute force to all direction then get the minimun of them all. i know the solution to the probelem i just want to know why my brute force don’t work . thanks for answer tho :slight_smile: .

#6

yes , i used to do just #include<bits/stdc++.h> why i used codeblocks but i switched to vs and i don’t use MINGW c++ compiler so i can’t use this include rather i just include all others :stuck_out_tongue:, thanks for point out that :slight_smile:

#7

sorry it’s my first time posting someting here , i just started to follow the guide , to improve more , and it’s not about the pb statement , more about i can’t found why my brute force have an infinte loop ,tho everything seems done with the right conditions. thanks for your reply :slight_smile:

#8

Can you please fix the formatting of your code though?

#9

Didn’t see that it was brute force the first time. The brute force looks correct, the only issue is that the brute force is exponential time (I would estimate something like 2^n where n is the number of squares). This is long enough to look like an infinite loop.