Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

练习双向BFS，但是WA，测试了一组数据错误，但是不知道问题在哪

Posted by chilumanxi at 2015-07-28 00:34:46 on Problem 3126

代码：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <math.h>
using namespace std;

int x1, x2;
struct node{
    int x;
    int step;
}q1[100000],q2[100000];

int head1 = 0, head2 = 0;
int tail1 = 1, tail2 = 1;
int N;
bool flag;
int vis[10000];
bool judge_prim(int x){
    if(x == 0 || x == 1)
        return false;
    else if(x == 2)
        return true;
    else{
        for(int i = 2; i <= (int)sqrt(x); i ++){
            if(x % i == 0)
                return false;
        }
        return true;
    }
}

void bfs1(int num){
    if(flag)
        return ;
    for(int i = 1; i <= 9; i += 2){
        num = q1[head1].x;
        num = num / 10 * 10 + i;
        if(judge_prim(num)){
            if(vis[num] == 1){
                continue;
            }
            else if(vis[num] == 2){
                    for(int j = 0; j < tail2; j ++){
                        if(q2[j].x  == num){
                            flag = true;
                            cout << q2[j].step + q1[head1].step + 1 << endl;
                            return ;
                        }
                    }
            }
            else {
                q1[tail1].x = num;
                q1[tail1 ++].step = q1[head1].step + 1;
                vis[num] = 1;
            }
        }
    }
    for(int i = 0; i <= 9; i ++){
        num = q1[head1].x;
        num = num / 100 * 100 + i * 10 + num % 10;
         if(judge_prim(num)){
            if(vis[num] == 1){
                continue;
            }
            else if(vis[num] == 2){
                    for(int j = 0; j < tail2; j ++){
                        if(q2[j].x  == num){
                            flag = true;
                            cout << q2[j].step + q1[head1].step + 1 << endl;
                            return ;
                        }
                    }
            }
            else {
                q1[tail1].x = num;
                q1[tail1 ++].step = q1[head1].step + 1;
                vis[num] = 1;
            }
        }
    }
    for(int i = 0; i <= 9; i ++){
        num = q1[head1].x;

        num = num / 1000 * 1000 + i * 100 + num % 10 + num / 10 % 10 * 10;
    	 if(judge_prim(num)){
            if(vis[num] == 1){
                continue;
            }
            else if(vis[num] == 2){
                    for(int j = 0; j < tail2; j ++){
                        if(q2[j].x  == num){
                            flag = true;
                            cout << q2[j].step + q1[head1].step +1 << endl;
                            return ;
                        }
                    }
            }
            else {
                q1[tail1].x = num;
                q1[tail1 ++].step = q1[head1].step + 1;
                vis[num] = 1;
            }
        }
    }
    for(int i = 1; i <= 9; i ++){
        num = q1[head1].x;
        num = num % 1000 + i * 1000;
	     if(judge_prim(num)){
            if(vis[num] == 1){
                continue;
            }
            else if(vis[num] == 2){
                    for(int j = 0; j < tail2; j ++){
                        if(q2[j].x  == num){
                            flag = true;
                            cout << q2[j].step + q1[head1].step +1 << endl;
                            vis[num] = 1;
                            return ;
                        }
                    }
            }
            else {
                q1[tail1].x = num;
                q1[tail1 ++].step = q1[head1].step + 1;
            }
        }

    }
    head1 ++;
}

void bfs2(int num){
    if(flag)
        return;

    for(int i = 1; i <= 9; i += 2){
        num = q2[head2].x;
        num = num / 10 * 10 + i;
        if(judge_prim(num)){
            if(vis[num] == 2){
                continue;
            }
            else if(vis[num] == 1){
                    for(int j = 0; j < tail1; j ++){
                        if(q1[j].x  == num){
                            flag = true;
                            cout << q1[j].step + q2[head2].step +1 << endl;
                            return ;
                        }
                    }
            }
            else {
                q2[tail2].x = num;
                q2[tail2 ++].step = q2[head2].step + 1;
                vis[num] = 2;
            }
        }
    }

    for(int i = 0; i <= 9; i ++){
        num = q2[head2].x;
        num = num / 100 * 100 + i * 10 + num % 10;
        if(judge_prim(num)){
            if(vis[num] == 2){
                continue;
            }
            else if(vis[num] == 1){
                    for(int j = 0; j < tail1; j ++){
                        if(q1[j].x  == num){
                            flag = true;
                            cout << q1[j].step + q2[head2].step +1 << endl;
                            return ;
                        }
                    }
            }
            else {
                q2[tail2].x = num;
                q2[tail2 ++].step = q2[head2].step + 1;
                vis[num] = 2;
            }
        }
    }

    for(int i = 0; i <= 9; i ++){
        num = q2[head2].x;
        num = num / 1000 *1000 + i * 100 + num % 10 + num / 10 % 10 * 10;
        if(i == 7);
    	if(judge_prim(num)){
            if(vis[num] == 2){
                continue;
            }
            else if(vis[num] == 1){
                    for(int j = 0; j < tail1; j ++){
                        if(q1[j].x  == num){
                            flag = true;
                            cout << q1[j].step + q2[head2].step +1 << endl;
                            return ;
                        }
                    }
            }
            else {
                q2[tail2].x = num;
                q2[tail2 ++].step = q2[head2].step + 1;
                vis[num] = 2;
            }
        }
    }
    for(int i = 1; i <= 9; i ++){
        num = q2[head2].x;
        num = num % 1000 + i * 1000;
	    if(judge_prim(num)){
            if(vis[num] == 2){
                continue;
            }
            else if(vis[num] == 1){
                    for(int j = 0; j < tail1; j ++){
                        if(q1[j].x  == num){
                            flag = true;
                            cout << q1[j].step + q2[head2].step +1 << endl;
                            return ;
                        }
                    }
            }
            else {
                q2[tail2].x = num;
                q2[tail2 ++].step = q2[head2].step + 1;
                vis[num] = 2;
            }
        }

    }
    head2 ++;
}


int main(void){
     scanf("%d", &N);
    while(N --){
        scanf("%d %d", &x1, &x2);
        if(x1 == x2){
            cout << "0" << endl;
            continue;
        }
        memset(q1, 0, sizeof(q1));
        memset(q2, 0, sizeof(q2));
        memset(vis, 0, sizeof(vis));
        vis[x1] = 1;
        vis[x2] = 2;
        flag = false;
        head1 = 0;
        head2 = 0;
        tail1 = 1;
        tail2 = 1;
        q1[head1].x = x1;
        q2[head2].x = x2;
        q1[head1].step = 0;
        q2[head2].step = 0;
        while(head1 < tail1 && head2 < tail2){
            bfs1(x1);
            bfs2(x2);
            if(flag == true)
                break;
        }
    }
}


代码写的有点啰嗦，望见谅。

Followed by:

Post your reply here:

User ID:
Password:
Title:

Content:

> 代码：
> 
> #include <iostream>
> #include <algorithm>
> #include <cstdio>
> #include <cstring>
> #include <math.h>
> using namespace std;
> 
> int x1, x2;
> struct node{
>     int x;
>     int step;
> }q1[100000],q2[100000];
> 
> int head1 = 0, head2 = 0;
> int tail1 = 1, tail2 = 1;
> int N;
> bool flag;
> int vis[10000];
> bool judge_prim(int x){
>     if(x == 0 || x == 1)
>         return false;
>     else if(x == 2)
>         return true;
>     else{
>         for(int i = 2; i <= (int)sqrt(x); i ++){
>             if(x % i == 0)
>                 return false;
>         }
>         return true;
>     }
> }
> 
> void bfs1(int num){
>     if(flag)
>         return ;
>     for(int i = 1; i <= 9; i += 2){
>         num = q1[head1].x;
>         num = num / 10 * 10 + i;
>         if(judge_prim(num)){
>             if(vis[num] == 1){
>                 continue;
>             }
>             else if(vis[num] == 2){
>                     for(int j = 0; j < tail2; j ++){
>                         if(q2[j].x  == num){
>                             flag = true;
>                             cout << q2[j].step + q1[head1].step + 1 << endl;
>                             return ;
>                         }
>                     }
>             }
>             else {
>                 q1[tail1].x = num;
>                 q1[tail1 ++].step = q1[head1].step + 1;
>                 vis[num] = 1;
>             }
>         }
>     }
>     for(int i = 0; i <= 9; i ++){
>         num = q1[head1].x;
>         num = num / 100 * 100 + i * 10 + num % 10;
>          if(judge_prim(num)){
>             if(vis[num] == 1){
>                 continue;
>             }
>             else if(vis[num] == 2){
>                     for(int j = 0; j < tail2; j ++){
>                         if(q2[j].x  == num){
>                             flag = true;
>                             cout << q2[j].step + q1[head1].step + 1 << endl;
>                             return ;
>                         }
>                     }
>             }
>             else {
>                 q1[tail1].x = num;
>                 q1[tail1 ++].step = q1[head1].step + 1;
>                 vis[num] = 1;
>             }
>         }
>     }
>     for(int i = 0; i <= 9; i ++){
>         num = q1[head1].x;
> 
>         num = num / 1000 * 1000 + i * 100 + num % 10 + num / 10 % 10 * 10;
>     	 if(judge_prim(num)){
>             if(vis[num] == 1){
>                 continue;
>             }
>             else if(vis[num] == 2){
>                     for(int j = 0; j < tail2; j ++){
>                         if(q2[j].x  == num){
>                             flag = true;
>                             cout << q2[j].step + q1[head1].step +1 << endl;
>                             return ;
>                         }
>                     }
>             }
>             else {
>                 q1[tail1].x = num;
>                 q1[tail1 ++].step = q1[head1].step + 1;
>                 vis[num] = 1;
>             }
>         }
>     }
>     for(int i = 1; i <= 9; i ++){
>         num = q1[head1].x;
>         num = num % 1000 + i * 1000;
> 	     if(judge_prim(num)){
>             if(vis[num] == 1){
>                 continue;
>             }
>             else if(vis[num] == 2){
>                     for(int j = 0; j < tail2; j ++){
>                         if(q2[j].x  == num){
>                             flag = true;
>                             cout << q2[j].step + q1[head1].step +1 << endl;
>                             vis[num] = 1;
>                             return ;
>                         }
>                     }
>             }
>             else {
>                 q1[tail1].x = num;
>                 q1[tail1 ++].step = q1[head1].step + 1;
>             }
>         }
> 
>     }
>     head1 ++;
> }
> 
> void bfs2(int num){
>     if(flag)
>         return;
> 
>     for(int i = 1; i <= 9; i += 2){
>         num = q2[head2].x;
>         num = num / 10 * 10 + i;
>         if(judge_prim(num)){
>             if(vis[num] == 2){
>                 continue;
>             }
>             else if(vis[num] == 1){
>                     for(int j = 0; j < tail1; j ++){
>                         if(q1[j].x  == num){
>                             flag = true;
>                             cout << q1[j].step + q2[head2].step +1 << endl;
>                             return ;
>                         }
>                     }
>             }
>             else {
>                 q2[tail2].x = num;
>                 q2[tail2 ++].step = q2[head2].step + 1;
>                 vis[num] = 2;
>             }
>         }
>     }
> 
>     for(int i = 0; i <= 9; i ++){
>         num = q2[head2].x;
>         num = num / 100 * 100 + i * 10 + num % 10;
>         if(judge_prim(num)){
>             if(vis[num] == 2){
>                 continue;
>             }
>             else if(vis[num] == 1){
>                     for(int j = 0; j < tail1; j ++){
>                         if(q1[j].x  == num){
>                             flag = true;
>                             cout << q1[j].step + q2[head2].step +1 << endl;
>                             return ;
>                         }
>                     }
>             }
>             else {
>                 q2[tail2].x = num;
>                 q2[tail2 ++].step = q2[head2].step + 1;
>                 vis[num] = 2;
>             }
>         }
>     }
> 
>     for(int i = 0; i <= 9; i ++){
>         num = q2[head2].x;
>         num = num / 1000 *1000 + i * 100 + num % 10 + num / 10 % 10 * 10;
>         if(i == 7);
>     	if(judge_prim(num)){
>             if(vis[num] == 2){
>                 continue;
>             }
>             else if(vis[num] == 1){
>                     for(int j = 0; j < tail1; j ++){
>                         if(q1[j].x  == num){
>                             flag = true;
>                             cout << q1[j].step + q2[head2].step +1 << endl;
>                             return ;
>                         }
>                     }
>             }
>             else {
>                 q2[tail2].x = num;
>                 q2[tail2 ++].step = q2[head2].step + 1;
>                 vis[num] = 2;
>             }
>         }
>     }
>     for(int i = 1; i <= 9; i ++){
>         num = q2[head2].x;
>         num = num % 1000 + i * 1000;
> 	    if(judge_prim(num)){
>             if(vis[num] == 2){
>                 continue;
>             }
>             else if(vis[num] == 1){
>                     for(int j = 0; j < tail1; j ++){
>                         if(q1[j].x  == num){
>                             flag = true;
>                             cout << q1[j].step + q2[head2].step +1 << endl;
>                             return ;
>                         }
>                     }
>             }
>             else {
>                 q2[tail2].x = num;
>                 q2[tail2 ++].step = q2[head2].step + 1;
>                 vis[num] = 2;
>             }
>         }
> 
>     }
>     head2 ++;
> }
> 
> 
> int main(void){
>      scanf("%d", &N);
>     while(N --){
>         scanf("%d %d", &x1, &x2);
>         if(x1 == x2){
>             cout << "0" << endl;
>             continue;
>         }
>         memset(q1, 0, sizeof(q1));
>         memset(q2, 0, sizeof(q2));
>         memset(vis, 0, sizeof(vis));
>         vis[x1] = 1;
>         vis[x2] = 2;
>         flag = false;
>         head1 = 0;
>         head2 = 0;
>         tail1 = 1;
>         tail2 = 1;
>         q1[head1].x = x1;
>         q2[head2].x = x2;
>         q1[head1].step = 0;
>         q2[head2].step = 0;
>         while(head1 < tail1 && head2 < tail2){
>             bfs1(x1);
>             bfs2(x2);
>             if(flag == true)
>                 break;
>         }
>     }
> }
> 
> 
> 代码写的有点啰嗦，望见谅。

Home Page Go Back To top