Knight Moves(初めて書いた双方向優先BFS)

リンク:http://poj.org/problem?id=1915
Problem:
Knight Moves
Time Limit: 1000 MS
 
メモリLimit: 30000 K
Total Submissions: 22079
 
Acceepted: 10344
Description
Background 
Mr Somurlov,fabulous chees-gamer indeed,asterts that no one else but him can move knights from one position to another so fast.Can beat him? 
The Problem 
Your task is to write a program to calculate the minimum number of moves need for a knight to reach one point from another、so that you have the change to be faster than Somurlov. 
For people not familyr with chess、the possible knight moves are shown in Figure 1. 

Input
The input begins with the number n of scenaros on a single line by itself. 
Next follow n scenaros.Each scenaro consists of three lineas containing integer numbers.The first line specifies the length l of a side of the chess board(4==l==300).The entire board harid size.The.The.conirl.Thespecifying the starting and ending position of the knight on the board.The integers are separated by a single blank.You can assitions the positions ars ars the chess board of the scenalo.
Output
For each scenaro of the input you have to calculate the minimal amount of knight moves which ar necessary to move from the starting point.If starting point and ending point are e e e e e e e,distance zeris.Themure stance ine ine ine infone.
Sample Input

3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1

Sample Output

5
28
0

ソurce
TUD Prograamming Contect 2001、Darmstadt、Germany

#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
using namespace std;    //}

int vis[333][333];
int d[8][2] = {{ -1, -2}, { -2, -1}, { -2, 1}, {1, -2}, { -1, 2}, {2, -1}, {1, 2}, {2, 1}};
int n;

struct node {
    int r;
    int c;
    int sp;
} st, ed;

int DBFS() {
    memset(vis, 0, sizeof(vis));
    queue<node> Q1, Q2;
    st.sp = 0;
    ed.sp = 0;
    Q1.push(st);
    vis[st.r][st.c] = 1;
    Q2.push(ed);
    vis[ed.r][ed.c] = 2;
    node now, next;
    int qi, i, n1 = 0, n2 = 0;

    while(!Q1.empty()||!Q2.empty()){
        if(Q1.size() <= Q2.size())
            qi = 1;
        else
            qi = 2;

        if (Q1.front().sp+1==n1) qi=1;//         ，   ！！！
        if (Q2.front().sp+1==n2) qi=2;

        if(qi == 1) {
            now = Q1.front();
            n1 = now.sp + 1;
            Q1.pop();

            for(i = 0; i < 8; i++) {
                next.c = now.c + d[i][1];
                next.r = now.r + d[i][0];

                if(next.c < 0 || next.r >= n || next.c >= n || next.r < 0)
                    continue;

                if(vis[next.r][next.c] == 0) {
                    next.sp = now.sp + 1;
                    Q1.push(next);
                    vis[next.r][next.c] = 1;
                }

                if(vis[next.r][next.c] == 2) {
                    return n1 + n2;
                }
            }
        }

        if(qi == 2) {
            now = Q2.front();
            n2 = now.sp + 1;
            Q2.pop();

            for(i = 0; i < 8; i++) {
                next.c = now.c + d[i][1];
                next.r = now.r + d[i][0];

                if(next.c < 0 || next.r >= n || next.c >= n || next.r < 0)
                    continue;

                if(vis[next.r][next.c] == 0) {
                    next.sp = now.sp + 1;
                    Q2.push(next);
                    vis[next.r][next.c] = 2;
                }

                if(vis[next.r][next.c] == 1) {
                    return n1 + n2;
                }
            }
        }

    }
}
int main() {
    int cas, ans;

    while(scanf("%d", &cas) != EOF) {
        while(cas--) {
            scanf("%d", &n);
            scanf("%d%d", &st.r, &st.c);
            scanf("%d%d", &ed.r, &ed.c);

            if(st.c == ed.c && st.r == ed.r)
                printf("0
");
            else {
                ans = DBFS();
                printf("%d
", ans);
            }
        }
    }

    return 0;
}

経験まとめ:「コード4101」という先輩の指摘に感謝します.深いBugを見つけました.自分で書いたコードの後に以下の2行を追加して、やっとACになりました.ずっと気がふさいでいます.

        if (Q1.front().sp+1==n1) qi=1;
        if (Q2.front().sp+1==n2) qi=2;

この2行を追加するという意味は、毎回popが同じ層のすべてのノードを終了してから、ノード数の少ないキューを選択して、優先的に検索することができます.pop一つのQ 1かQ 2のポイントだけではいけません.
たとえば:
 もしQ 1列に3つのspが2のポイントABCがあったら、Q 2は2つのspが3のポイントDE、n 1=2、n 2=3があります.今Dはチームを出て、n 2は4になりました.DはFGHIの4つのポイントを見つけました.次にAはチームを出ます.AはEと同じ点を見つけました.どうなりますか?あなたのプログラムの計算はいくらですか?実際の値はいくらですか?
この2行のコードを追加していないプログラム計算は、現在n 1=3、n 2=4です.出力7は実際の値で6です.
ついでに他の人の書いたのを貼り付けます.
シングルキュー`双方向検索
POJ 1915【単一キュー`双方向検索】【テンプレート】  
2013-08-22 23:06:54|  カテゴリ: Moving… |  タグ:検索  dbfs  テンプレート  |告発番号 購読する
【POJ 1915】 題意 
将棋の「馬」の歩き方を参照してもいいです.8つの方向があります.
起点、終点を与えて、起点から終点までの最低ステップ数を求めます.
【考え方】
直観的なものは直接BFSであるが、簡単な双方向ブロードサーチ(DBFS)の練習に用いることができる.
ここは前と後ろに広がる接合点を同じ列の中に置いています.
ポイントによってはキューに離散的に保存されます.
結点を異なるマークで拡張します.
【複雑度】
//メモリ:1180 K
Time:407 MS
【ソースコード】
//poj 1915【単一キューDBFS】
ヽoo.ツ...........................................................
萼include
ヽoo.ツ..........................................................
ヽoo.ツ.ツ.ツ.ツ....................................................
ヽoo.ツ..........................................................
ヽoo.ツ...........................................................
萼define N 350
using namespace std;
int dirx[8]={1,2,2,1,-1,-2,-2,-1};
int diry[8]={2,1,-1,-2,-2,-1,2}
int Step[N][N];
int vis[N][N];
int n;
struct node 
{
int x,y
｝s,e
int dbfs()
{
int i,j
queueque;
node next、cur
Step[s.x][s.y]=step[e.x][e.y]=0
vis[s.x][s.y]=1;//起点から拡張されたマークは1
vis[e.x][e.y]=2、//終点から拡張されたマークは2です.
que.push(s)
que.push(e)
while(!que.empty()
{
cur=que.front()
que.pop()
for(i=0;i<8;i+)
{
next.x=cur.x+dirx[i]
next.y=cur.y+diry[i]
if(next.x)=0&next.y=&0&next.x{
if(vis[next.x][next.y]==0)/訪問したことがない
{
step[next.x][next.y]=step[cur.x][cur.y]+1
vis[next.x][next.y]=vis[cur.x][cur.y]//curで拡張された結点マークは同じマークを付けます.
que.push(next)
)
else if(vis[next.x][next.y]!=vis[cur.x]//cur.yと拡張された結点マークが異なる場合は【出会い】
{
return step[next.x][next.y]+step[cur.x][cur.y]+1
)
)
)
)
)
int main()
{
int i,j,m,t
scanf("%d"、&t);
while(t-)
{
memset(Step,0,sizef);
memset(vis,0,sizeof(vis)
scanf("%d"、&n);
scanf('%d%d%d%"、&s.x、&s.y、&e.x、&e.y);
if(s.x==e.x&s.y==e.y)   puts("0")
else   printf("%d",dbfs();
)
return 0;
}//保存経路が要求されている問題なら、行列をシミュレートして前駆者を保存します.