希望bobo老师可以帮我看一下T T

Question

bobo老师你好呀 ！！
是这样的，我在做学校OJ上面的题目的时候，发现了一道题目，跟这个题目非常相似，基本思路一模一样。写完之后，测试了几个testcase也都是对的。但是提交问题的时候却是WA，我de了很久bug但是找不出来，也没有多的testcase可以测试了。不知道bobo老师能不能帮我看一下。麻烦bobo老师了o(╥﹏╥)o

这是题目描述：

#include <iostream>
#include <vector>
#include <unordered_set>
#include <queue>
#include <string>
#include <cmath>
#include <unordered_map>

using namespace std;

unordered_set<int> getAllPrim(){
    
    unordered_set<int> res;
    for ( int i = 1000 ; i <= 9999; i ++ ) {
        
        bool sumNumber = false;
        for ( int j = 2 ; j < sqrt(i) ; j ++ )
            if ( i % j == 0 ) {
                sumNumber = true;
                break;
            }
        
        if ( !sumNumber )
            res.insert( i );
        
    }
    return res;
}

const unordered_set<int> record = getAllPrim();

vector<int> getNexts( int cur ){
    
    vector<int> res;
    string curs = to_string( cur );
    for ( int i = 0 ; i < 4 ; i ++ ) {
        
        char o = curs[i];
        if ( i == 0 ) {
            for ( int j = 1 ; j <= 9 ; j ++ ) {
                curs[i] = (curs[i] - '0' + j) % 10 + '0';
                if ( curs[i] != '0' &&
                    record.find( atoi( curs.c_str() ) ) != record.end() )
                    res.push_back( atoi( curs.c_str() ) );
                
                curs[i] = o;
            }
        }
        else
            for ( int j = 1 ; j <= 9 ; j ++ ) {
                curs[i] = (curs[i] - '0' + j) % 10 + '0';
                if ( record.find( atoi( curs.c_str() ) ) != record.end() )
                    res.push_back( atoi( curs.c_str() ) );
                
                curs[i] = o;
            }
        
    }
    
    return res;
}

int main(int argc, const char * argv[]) {
    
    int N;
    cin >> N ;

    while ( N -- ) {
        
        int start, end;
        cin >> start >> end;
        
        int res = 0;
        
        if ( record.find( start ) == record.end() || record.find( end ) == record.end() ) {
            cout << "Impossible" << endl;
            continue;
        }
        
        if ( start == end ) {
            cout << res << endl;
            break;
        }
        
        queue<int> q;
        unordered_map<int, int> visited;
        q.push( start );
        visited[start] = 0;
        
        bool find = false;
        while ( !q.empty() && !find ) {
            
            int curN = q.front();
            q.pop();
            
            vector<int> nexts = getNexts( curN );
            
            for ( int next: nexts )
                if ( visited.find( next ) == visited.end() ){
                    q.push( next );
                    visited[next] = visited.at( curN ) + 1;
                    if ( next == end ) {
                        res = visited.at( next );
                        find = true;
                        break;
                    }
                }
            
        }
        
        if ( find )
            cout << res << endl;
        else
            cout << "Impossible" << endl;
        
    }
    
    return 0;
}

插一句：bobo老师真的教的太好了！我第一次见这个题目就想到了bobo老师讲的这个题目，而且做得时候还很流畅（虽然WA了T T）

Answer 1

liuyubobobo 2020-09-06 09:21:35

题目 OJ 的地址链接给我一下？是任何人员都可以访问的吗？

• 提问者 2020要好好努力0_0 #1

  不好意思！学校那个OJ不是所有人都可以访问哒，需要学生证，感谢bobo老师费心。
  不过我已经发现了我的BUG啦！不是bobo老师教的bfs主逻辑的问题。是我在求解1000-9999所有质数的函数中，
  for ( int i = 1000 ; i <= 9999; i ++ ) {
          
          bool sumNumber = false;
          for ( int j = 2 ; j < (=)(少加了这个等于号)sqrt(i) ; j ++ )
              if ( i % j == 0 ) {
                  sumNumber = true;
                  break;
              }
          
          if ( !sumNumber )
              res.insert( i );
          
      }
  其余的部分都没有问题！（bobo老师教的好
  再次感谢bobo老师（笔芯

• liuyubobobo 回复 提问者 2020要好好努力0_0 #2

  赞！继续加油！：）

Answer 2

提问者 2020要好好努力0_0 2020-09-05 20:41:37

刚刚发现了一个bug:

        if ( start == end ) {
           cout << res << endl;
           break;
       }

这里我改成了continue;

但还是WA了:-(