Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## g++ tle, c++ac球原因

Posted by Alextokc at 2017-05-18 12:45:06 on Problem 3126
```代码:
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <deque>
#include <queue>
#include <utility>
#include <iterator>

using namespace std;
const int Maxn = 10005;
int T;
bool isprime[Maxn];
bool vis[Maxn];
typedef pair < string, int> node;

string a, b;

inline void prime_sieve(int n) {
memset(isprime, 1, sizeof isprime);
int i, j;
isprime[0] = 0, isprime[1] = 0;
for (i = 2; i <= n; ++i) {
if (isprime[i])
for (j = i + i; j <= n; j += i)
isprime[j] = 0;
}
}

inline int strtonum(string x) {
int num = 0, i;
if (x[0] == '-') {
for (i = 1; i < x.length(); ++i)
num = num * 10 + (x[i] - '0');
return -num;
}
for (i = 0; i < x.length(); ++i)
num = num * 10 + (x[i] - '0');
return num;
}

inline bool check(int num) {
if (num == strtonum(b)|| (num & 1 && isprime[num] && vis[num] == 0 && num >= 0 && num <= 9999))
return true;
return false;
}

inline int bfs() {

queue < node > Q;
node x;
x.first = a, x.second = 0;
Q.push(x);
vis[strtonum(x.first)] = 1;

int i, j, numberx;
node next;
while (!Q.empty()) {
x = Q.front(); Q.pop();
if (x.first == b) return x.second;
for (i = 0; i < 4; ++i) {
if (i == 0) {
for (j = 1; j <= 9; ++j) {
next = x;
next.first[0] = (j + '0');
numberx = strtonum(next.first);
if (check(numberx)) {
vis[numberx] = 1;
next.second = x.second + 1;
Q.push(next);
}
}
} else if (i == 1) {
for (j = 0; j <= 9; ++j) {
next = x;
next.first[1] = (j + '0');
numberx = strtonum(next.first);
if (check(numberx)) {
vis[numberx] = 1;
next.second = x.second + 1;
Q.push(next);
}
}
} else if (i == 2) {
for (j = 0; j <= 9; ++j) {
next = x;
next.first[2] = (j + '0');
numberx = strtonum(next.first);
if (check(numberx)) {
vis[numberx] = 1;
next.second = x.second + 1;
Q.push(next);
}
}
} else if (i == 3) {
for (j = 1; j <= 9; j += 2) {
next = x;
next.first[3] = (j + '0');
numberx = strtonum(next.first);
if (check(numberx)) {
vis[numberx] = 1;
next.second = x.second + 1;
Q.push(next);
}
}
}
}
}
return -1;
}

int main() {
ios::sync_with_stdio(false);
prime_sieve(Maxn);
cin >> T;
while (T--) {
memset(vis, 0, sizeof vis);
cin >> a >> b;
int X;
X = bfs();
if (X == -1) cout << "Impossible" << endl;
else cout << X << endl;
}
return 0;
}

Followed by: