最近才学会bfs，写了蛮长的代码，验样例的时候虽然都是对的，但是还是有点没把握，以为要卡，没想到过了。
思路是将这个四位数拆分成四个整形变量，逐个对四个数字分别用0~9之间（千位数特殊：1~9）除本身的数字替换，替换单个数字之后的四位数的数必须是之前没有变换到的数（用vis[]数组检查状态），检查是否为素数。
贴一下bfs的代码，有点长，如果有错误请大佬们指点！

void bfs(int start, int e) {
  t1.num = start;
  t1.ans = 0;
  vis[t1.num] = 1;
  q.push(t1);
  while (!q.empty()) {
    t1 = q.front();  
    q.pop();
    int temp,a,b,c,d;
    for (int i = 0; i < 4; i++) {
      d = t1.num%10;c = t1.num/10%10;
      b = t1.num/100%10; a = t1.num/1000;
      if (i == 0) {
        for(int j = 1; j <= 9; j++) {
          if (j != a) {
            temp = j*1000+b*100+c*10+d;
            if (check(temp) && !vis[temp]) {
              t2.num = temp;
              t2.ans = t1.ans+1;
              if (t2.num == e) {
                printf("%d\n", t2.ans);
                return;
              }
              vis[t2.num] = 1;
              q.push(t2);
            }
          }
        }
      } 
      if (i == 1) {
        for (int j = 0; j <= 9; j++) {
          if (j != b) {
            temp = a*1000+j*100+c*10+d;
            if (check(temp) && !vis[temp]) {
              t2.num = temp;
              t2.ans = t1.ans+1;
              if (t2.num == e) {
                printf("%d\n", t2.ans);
                return;
              }
              vis[t2.num] = 1;
              q.push(t2);
            }
          }
        }
      }
      if (i == 2) {
        for (int j = 0; j <= 9; j++) {
          if (j != c) {
            temp = a*1000+b*100+j*10+d;
            if (check(temp) && !vis[temp]) {
              t2.num = temp;
              t2.ans = t1.ans+1;
              if (t2.num == e) {
                printf("%d\n", t2.ans);
                return;
              }
              vis[t2.num] = 1;
              q.push(t2);
            }
          }
        }
      }
      if (i == 3) {
        for (int j = 0; j <= 9; j++) {
          if (j != d) {
            temp = a*1000+b*100+c*10+j;
            if (check(temp) && !vis[temp]) {
              t2.num = temp;
              t2.ans = t1.ans+1;
              if (t2.num == e) {
                printf("%d\n", t2.ans);
                return;
              }
              vis[t2.num] = 1;
              q.push(t2);
            }
          }
        }
      }
    }   
  }
} 

• Re:吃鲸！感觉写了好长的代码，居然一遍过了w(ﾟДﾟ)w (55) xvxiaoya 2019-11-18 23:08:04