Jun 2022
1 / 9
Jun 2022
Jun 2022
harsh1224
Jun '22

(First post on SPOJ)
Getting wrong ans for this problem :slight_smile:

https://www.spoj.com/problems/SPIKES/11

I am using Dijkstra algorithm.
Thanks in advance.

#include<bits/stdc++.h>
using namespace std;

// # = 35
// @ = 64
// . = 46
// s = 115

int n,m,j; 
const int N = 100;
const int INF = 1e9+10;
vector<int> g[N];
int vis[N][N];
pair<int,int> dist[N][N];

vector<pair<int,int>> movements = {
    {0,1},{0,-1},{1,0},{-1,0}
};

bool isvalid(int i, int j){
    return i>=0 && j>=0 && i<n && j<m;
}

void bfs(int sourcei, int sourcej){
    set<pair<int,pair<int,int>>> q;
    q.insert({0,{sourcei,sourcej}});
    dist[sourcei][sourcej] = {0,INF};
    while(q.size()>0){
        auto curr_v = *q.begin();
        int curr_i = (curr_v.second).first;
        int curr_j = (curr_v.second).second;
        int spikes = curr_v.first;
        q.erase(q.begin());

        if(vis[curr_i][curr_j]) continue;
        vis[curr_i][curr_j] = 1;
        for(auto m : movements){
            int child_i = curr_i + m.first;
            int child_j = curr_j + m.second;
            int spikec = spikes;
            if(!isvalid(child_i,child_j)) continue;
            if(g[child_i][child_j] == 115) spikec = spikes+1;
            if(vis[child_i][child_j]) continue;
            if(g[child_i][child_j]==35) continue;

            if(dist[child_i][child_j].second > spikec){
                dist[child_i][child_j] = {(dist[curr_i][curr_j].first +1),spikec};
                q.insert({spikec , {child_i,child_j}});
            }
        }
    }
}

int main(){
    cin>>n>>m>>j;
    int start_j,start_i;
    int end_j,end_i;

    for (int i = 0; i < N; ++i){
        for (int j = 0; j < N; ++j){
            dist[i][j].second = INF;
            dist[i][j].first = 0;
        }
    }

    for (int i = 0; i < n; ++i){
        for (int j = 0; j < m; ++j){
            char x; cin>>x;
            g[i].push_back((int)x);
            if(x=='@') {
                start_i = i;
                start_j = j;
            }
            if(x=='x'){
                end_i = i;
                end_j = j;
            }
        }
    }
    
    bfs(start_i,start_j);

    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            cout<<dist[i][j].first<<","<<dist[i][j].second<<" ";
        }cout<<endl;
    }

    if(dist[end_i][end_j].second <= (int)j/2) cout<<"SUCCESSFUL"<<endl;
    else cout<<"IMPOSSIBLE"<<endl;
       
}

  • created

    Jun '22

  • last reply

    Jun '22
  • 8

    replies

  • 704

    views

  • 2

    users

  • 1

    like

  • 2

    links

simes
Jun '22

Did you miss that bit?

harsh1224
Jun '22
1

Completely man!!!
Thanks a lot!

I thought imma never get a reply on spoj forums…

harsh1224
Jun '22
simes

@simes Thanks for helping. Bro I just modified the code into multisource dijkstra
Still getting WA. can you please provide some crucial testcases.

#include<bits/stdc++.h>
using namespace std;

// # = 35
// @ = 64
// . = 46
// s = 115

int n,m,j; 
const int N = 100;
const int INF = 9;
vector<int> g[N];
int vis[N][N];
pair<int,int> dist[N][N];
vector<pair<int,int>> exits;

vector<pair<int,int>> movements = {
    {0,1},{0,-1},{1,0},{-1,0}
};

bool isvalid(int i, int j){
    return i>=0 && j>=0 && i<n && j<m;
}

void bfs(){
    int sourcei,sourcej;
    set<pair<int,pair<int,int>>> q;

    for(auto pr:exits){
        sourcei = pr.first;
        sourcej = pr.second;
        q.insert({0,{sourcei,sourcej}});
        dist[sourcei][sourcej] = {0,INF};
    }

    while(q.size()>0){
        auto curr_v = *q.begin();
        int curr_i = (curr_v.second).first;
        int curr_j = (curr_v.second).second;
        int spikes = curr_v.first;
        q.erase(q.begin());

        if(vis[curr_i][curr_j]) continue;
        vis[curr_i][curr_j] = 1;

        for(auto m : movements){
            int child_i = curr_i + m.first;
            int child_j = curr_j + m.second;
            int spikec = spikes;
            if(!isvalid(child_i,child_j)) continue;
            if(g[child_i][child_j] == 115) spikec = spikes+1;
            if(vis[child_i][child_j]) continue;
            if(g[child_i][child_j]==35) continue;

            if(dist[child_i][child_j].second > spikec){
                dist[child_i][child_j] = {(dist[curr_i][curr_j].first +1),spikec};
                q.insert({spikec , {child_i,child_j}});
            }
        }
    }
}

int main(){
    cin>>n>>m>>j;
    int end_j,end_i;

    for (int i = 0; i < N; ++i){
        for (int j = 0; j < N; ++j){
            dist[i][j].second = INF;
            dist[i][j].first = 0;
        }
    }

    for (int i = 0; i < n; ++i){
        for (int j = 0; j < m; ++j){
            char x; cin>>x;
            g[i].push_back((int)x);
            if(x=='@') {
                exits.push_back({i,j});
            }
            if(x=='x'){
                end_i = i;
                end_j = j;
            }
        }
    }
    
    bfs();

    // for (int i = 0; i < n; ++i)
    // {
    //     for (int j = 0; j < m; ++j)
    //     {
    //         cout<<dist[i][j].first<<","<<dist[i][j].second<<" ";
    //     }cout<<endl;
    // }

    if(dist[end_i][end_j].second <= (int)j/2) cout<<"SUCCESS"<<endl;
    else cout<<"IMPOSSIBLE"<<endl;

    return 0;
}
simes
Jun '22

I can’t find a test case that fails, but I think I’ve spotted the problem. Consider a test case like this.

4 3 0
@#@
s#.
…
#x#

Now imagine the next position to be considered is r3c2, and for the sake of argument, say the current route came past the single spike. The treasure is reachable, but the spike limit is breached. However, the position r3c2 is marked as visited.

So, when the other route to the treasure, the one without the spike, reaches the same r3c2 position, it reaches this line:

if(vis[child_i][child_j]) continue;

finds the position has already been visited, and so doesn’t reach the treasure.

Now I can’t make this happen, but I think it can. It depends on the order that the queued items are processed, which depends on the order they’re extracted from the set. (btw, why use a set for the queue, rather than the more usual queue or vector?)

harsh1224
Jun '22

Thankyou for replying simes! I got your point.
But this has already been taken care of. you can try printing the entire distance array (the commented out code in main() function ). And the dijkstra is implemeted such a way that it will always choose the shortest “spike path”

I dont know what testcases are failing hope that some admin will reply soon. @adminek123 @admins

Its the way dijkstra works iguess. coz if I use queue, evrytime I’ll have to run an O(N) loop to extract the minimum element, while its less expensive if we use set.

simes
Jun '22
1

Ah I see, I hadn’t spotted that. I’m more used to seeing a priority queue used for that.

Edit: one of the comments seems to suggest you need to handle test cases with no treasure. I’m not convinced, but might be worth a try.

harsh1224
Jun '22

This was the problem bro! @simes
INF was supposed to be 1e9+10 while I set it to 9 while dry running the code (for the sake of avoiding big numbers)

Now it is accepted. LOL

That seems more of a typo.

BTW Thanks a lot for supporting!

simes
Jun '22

Well that explains it… I’m disappointed I didn’t spot it though!