Got 'wrong answer' but my code gives me the correct answer on my computer


  • 0
    N

    I tried to solve this problem in C++ using Bellman-Ford. Below is my code

    class Solution {
        const int INF = 0x3f3f3f3f;
    
    public:
        int openLock(vector<string>& deadends, string target) {
            vector<int> bf(10000, INF);
            int tar = atoi(target.c_str());
            bf[0] = 0;
            for (auto &s : deadends) {
                bf[atoi(s.c_str())] = -1;
            }
            for (int i = 0; i < 10000; ++i) {
                if (bf[i] == -1) continue;
                int d1 = i % 10;
                int d2 = (i/10) % 10;
                int d3 = (i/100) % 10;
                int d4 = (i/1000) % 10;
                int slist[] = {
                    i - d1 + (d1 + 1) % 10,
                    i - d1 + (d1 + 9) % 10,
                    i - 10*d2 + 10 * ((d2+1) % 10),
                    i - 10*d2 + 10 * ((d2+9) % 10),
                    i - 100*d3 + 100 * ((d3+1)%10),
                    i - 100*d3 + 100 * ((d3+9)%10),
                    i - 1000*d4 + 1000*((d4+1)%10),
                    i - 1000*d4 + 1000 *((d4+9)%10)                
                };
                int nw = bf[i]+1;
                for (int s : slist) {
                    if (bf[s] != -1 && nw < bf[s]){
                        bf[s] = nw;
                    }
                }
            }
            if (bf[tar] == INF) return -1;
            return bf[tar];
        }
    };
    

    on input

    deadends = ["1311","1032","3000","1113","3001","3112","2323","2113","1332","2100"]
    target = "2201"
    

    It said I got the wrong answer 9 instead of 5 but I ran it on my computer (with gcc 7.2), and I got the correct answer 5. I actually rewrote this code in python and encountered the same problem. Below is my code:

    class Solution:
        def openLock(self, deadends, target):
            """
            :type deadends: List[str]
            :type target: str
            :rtype: int
            """
            bf = [10000]*10000
            tar = int(target)
            bf[0] = 0
            for s in deadends:
                bf[int(s)] = -1
            for i in range(10000):
                if bf[i] == -1:
                    continue
                d1 = i%10
                d2 = (i//10)%10
                d3 = (i//100) % 10
                d4 = (i//1000) % 10
                slist = [
                    i - d1 + ((d1 + 1) % 10),
                    i - d1 + ((d1 + 9) % 10),
                    i - 10*d2 + 10 * ((d2+1) % 10),
                    i - 10*d2 + 10 * ((d2+9) % 10),
                    i - 100*d3 + 100 * ((d3+1)%10),
                    i - 100*d3 + 100 * ((d3+9)%10),
                    i - 1000*d4 + 1000*((d4+1)%10),
                    i - 1000*d4 + 1000 *((d4+9)%10)                
                ]
                nw = bf[i]+1
                for s in slist:
                    if bf[s] != -1 and nw < bf[s]:
                        bf[s] = nw
            if bf[tar] == 10000:
                return -1
            return bf[tar]
    

    Did I have a bug that behaves differently in different compilers?


Log in to reply
 

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