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

哪位能帮忙看一下,哪有逻辑错误,,,WA 不知为什么,

Posted by hebeimoumoumou at 2011-05-23 20:32:32 on Problem 2965
#include<iostream>
#include<queue>
#include<string.h>
#include<bitset>
#include<memory>
#include<cstdio>
using namespace std;

typedef bitset <16> piece;
int cnt;
struct Stat
{
    piece value;
    int index;
    Stat (piece x,int y):value(x),index(y){};
    Stat (){};
} ;
Stat stat,temp;



struct situation
{
    int step;
    int pre;
    int x;
    int y;
};

struct point
{
    int x;
    int y;
};
queue<Stat> q;
point index [70000];
situation store[70000];
bool visit[70000];

piece offset[16]={0xf888,0xf444,0xf222,0xf111,
                  0x8f88,0x4f44,0x2f22,0x1f11,
                  0x88f8,0x44f4,0x22f2,0x11f1,
                  0x888f,0x444f,0x222f,0x111f,};

void bfs(Stat start)
{   visit[start.value.to_ulong()]=true;
    memset(visit,false,sizeof(visit));//一定要在BFS 里面
    q.push (start);

    while(!q.empty())
    {
        stat=q.front();
        q.pop();
        if (stat.value.to_ulong()==0)
            {
                cout<<store[stat.index].step<<endl;
                int counter=0;
                for(int i=stat.index;store[i].pre!=-1;i=store[i].pre)
                     {
                         index[counter].x=store[i].x;
                         index[counter].y=store[i].y;
                         counter++;
                     }
                for(int i=counter-1;i>=0;i--)  cout<<index[i].x<<" "<<index[i].y<<endl;
                return ;
            }
        for(int i=1;i<=4;i++)
             for(int j=1;j<=4;j++)
                 {
                     temp.value=stat.value^offset[(i-1)*4+j-1];
                     if(!visit[temp.value.to_ulong()])
                        {
                            visit[temp.value.to_ulong()]=true;
                            q.push(temp);
                            temp.index=cnt;
                            store[cnt].x=i;
                            store[cnt].y=j;
                            store[cnt].pre=stat.index;
                            store[cnt].step=store[stat.index].step+1;
                            cnt++;
                        }
                 }
    }
}
int main()
{   freopen("in.txt","r",stdin);
    freopen ("out.txt","w",stdout );
    string g="";
    char ch;
    for(int i=0;i<4;i++)
       {
           for(int j=0;j<4;j++)
               {
                ch=getchar();
               if(ch=='-')  g+="0";
               else         g+="1";
               }
           getchar();
       }
    piece p(g);

    store[0].pre=-1;
    store[0].step=0;

    cnt=1;
    bfs(Stat(p,0));

    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator