C++ SPFA Solution beat 100% (currently)


  • 1
    S
    class Solution {
    public:
        string findShortestWay(vector<vector<int>>& a, vector<int>& ball, vector<int>& hole) {
            M = a.size();
            N = a[0].size();
            g = vector<vector<pair<int,int>>>(N*M,vector<pair<int,int>>{});
            for (int i = 0;i < M;i++) {
                for (int j = 0;j < N;j++) {
                    if (a[i][j]) continue;
                    for (int k = 0;k < 4;k++) {
                        int x = i;
                        int y = j;
                        int dist = 0;
                        while (x + dx[k] >= 0 && x + dx[k] < M && y + dy[k] >= 0 && y + dy[k] < N && !a[x+dx[k]][y+dy[k]]) {
                            x += dx[k];
                            y += dy[k];
                            dist++;
                            if (x == hole[0] && y == hole[1]) break;
                        }
                        g[enc(i,j)].push_back(make_pair(enc(x,y),dist));
                    }
                }
            }
            return bfs(enc(ball[0],ball[1]),enc(hole[0],hole[1]));
        }
    private:
        int enc(int i,int j) {
            return i * N + j;
        }
        int M;
        int N;
        int dx[4] = {-1,0,1,0};
        int dy[4] = {0,1,0,-1};
        vector<vector<pair<int,int>>> g;
        string name[4] = {"u","r","d","l"};
        string bfs(int S,int T) {
            vector<int> queue;
            queue.push_back(S);
            int p = 0;
            int q = 1;
            auto inqueue = vector<bool>(M * N, false);
            auto visited = vector<bool>(M * N, false);
            auto bestDist = vector<int>(M * N, 0);
            auto bestS = vector<string>(M * N,"");
            visited[S] = true;
            bestDist[S] = 0;
            bestS[S] = "";
            while (p < q) {
                int x = queue[p];
                int cDist = bestDist[x];
                string cRoute = bestS[x];
                p++;
                inqueue[x] = false;
                for (int k = 0;k < 4;k++)
                {
                    int y = g[x][k].first;
                    if (y == x) continue;
                    int nDist = cDist + g[x][k].second;
                    string nRoute = cRoute + name[k];
                    if (!visited[y] || nDist < bestDist[y] || (nDist == bestDist[y] && nRoute < bestS[y]))
                    {
                        if (!inqueue[y]) {
                            queue.push_back(y);
                            inqueue[y] = true;
                            q++;
                        }
                        visited[y] = true;
                        bestDist[y] = nDist;
                        bestS[y] = nRoute;
                    }
                }
            }
            if (!visited[T])
            return "impossible";
            else {
                return bestS[T];
            }
        }
    };
    

  • 0
    S

    @syb3181 the solution is two fold, first create a graph with its weight being the number of empty cells passed through, and then invoke SPFA on the weighed graph.
    Several Tips about SPFA:

    1. the queue contains at most one copy of each node, when it is popped, use the current best solution for that node, so that we needn't put the solution with node into the queue
    2. circled queue can be introduced to reduce the space cost, though in my opinion, it is needless

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.