RE, but works fine on my machine. What is the problem? Any help?


  • 0
    J
    #include <bits/stdc++.h>
    #define _ ios_base::sync_with_stdio(0);cin.tie(0);
    
    using namespace std;
    
    #define PI acos(-1)
    #define sqr(x) ((x) * (x))
    #define PB push_back
    #define MP make_pair
    #define F first
    #define S second
    #define ALL(c) (c).begin(), (c).end()
    #define SIZE(c) (int)(c).size()
    #define REP(i, a, b) for (int i = int(a); i <= int(b); i++)
    #define REPD(i, a, b) for (int i = int(a); i >= int(b); i--) 
    
    typedef unsigned long long ull;
    typedef long long ll;
    typedef pair<int,int> ii;
    typedef pair<double,double> dd;
    typedef vector<int> vi;
    typedef vector<vi> vvi;
    typedef vector<ii> vii;
    typedef vector<vii> vvii;
    typedef vector<string> vs;
    typedef map<int,int> mii;
    typedef map<string, int> msi;
    typedef set<int> si;
    
    vvi g;
    msi h;
    int S,F;
    const int INF=1<<28;
    
    class Solution {
    public:
        int ladderLength(string start, string end, unordered_set<string> &dict) {
            int n = SIZE(dict) + 2, v = 1, wl = start.length(), dist[n];
            bool disc[n];
            REP(i, 0, n-1) { disc[i]=false; dist[i]=INF; }
            queue<int> q;
            g.resize(n);
            
            for (unordered_set<string>::iterator it = dict.begin(); it != dict.end(); ++it) { 
                if(*it != start && *it != end) { 
                    h[*it]=v; 
                    v++; 
                }
            }
            S=0, F=v;
            
            char buf[wl+1];
            REP(i, 0, wl-1) {
                REP(j, 0, 25) {
                    strcpy(buf, start.c_str());
                    buf[i]='a'+j;
                    string sa(buf);
                    
                    if(h.find(sa)!=h.end() && sa != start) {
                        g[S].PB(h[sa]);
                        g[h[sa]].PB(S);
                    }
                    
                for (unordered_set<string>::iterator it = dict.begin(); it != dict.end(); ++it) {
                    if(*it == start || *it == end) { continue; }
                        strcpy(buf, (*it).c_str());
                        buf[i]='a'+j;
                        string sb(buf);
                        
                        if(h.find(sb)!=h.end()) {
                            g[h[*it]].PB(h[sb]);
                            g[h[sb]].PB(h[*it]);
                        }                  
                    }
                    
                    strcpy(buf, end.c_str());
                    buf[i]='a'+j;
                    string sc(buf);
                    
                    if(h.find(sc)!=h.end() && sc != end) {
                        g[F].PB(h[sc]);
                        g[h[sc]].PB(F);
                    }      
                    
                }
            }
            
            q.push(S);
            disc[S]=true;
            dist[S]=1; //path length is vertex count along path, not edges
    
            int u, y;
            while(!q.empty()) {
                u=q.front(); q.pop();
    
                REP(i, 0, SIZE(g[u])-1) {
                    y=g[u][i];
    
                    if(!disc[y]) {
                        if(y == F) {
                            dist[y] = min(dist[y], dist[u]+1);
                        }else {
                            q.push(y);
                            disc[y]=true;
                            dist[y]=dist[u]+1;
                        }
                    }
                }
            }
            
            if(dist[F] == INF) { return 0; }
            else { return dist[F]; }
        }
    };

Log in to reply
 

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