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

用的bfs+位运算,哪位大牛帮我看下哪里wa了吧,不胜受恩感激,实在是不知道了

Posted by Jason_Angela at 2010-04-08 17:59:07 on Problem 2965
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int id[70000],fa[70000],step[70000];
int find(int x)
{
   int dir[16] = {63624,62532,61986,61713,36744,20292,12066,7953,35064,17652,
                  8946,4593,34959,17487,8751,4383};
   queue<int>q;
   q.push(x);
   memset(step,-1,sizeof(step));
   memset(fa,-1,sizeof(fa));
   step[x] = 0;
   int cur,temp;
   while (!q.empty()){
   	  cur = q.front();
   	  q.pop();
   	  for (int i=0; i<16; i++){
  	     temp = cur ^ dir[i];
  	     if (step[temp]==-1){
     	    step[temp] = step[cur]+1;
     	    q.push(temp);
     	    id[temp] = i;
     	    fa[temp] = cur;
  	     }
  	     if (!temp) return step[temp];
   	  }
   }
} 
void Output(int x)
{ 
   if (fa[x]!=-1){
      Output(fa[x]);
      printf("%d %d\n",id[x]/4+1,id[x]%4+1);
   }
}
main()
{
   char map[6];
   int st = 0;
   for  (int i=1; i<=4; i++){
   	  scanf("%s",map);
   	  for (int j=0; j<4; j++){
  	     st <<= 1;
  	     if (map[j]=='+')
  	        st++;
   	  }
   }
   printf("%d\n",find(st));
   Output(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