Liny_@NotePad

沉迷ACG中

翻硬币游戏

YOYO posted @ 2009年5月12日 18:36 in 【ICPC】解题报告 with tags BFS , 2990 阅读

FJNU1969：http://acm.fjnu.edu.cn/show?problem_id=1969

这是我第一次参加的校赛里面的题目，当时一题也没做出来 囧。
现在也只会4题，55。

因为数据很弱，暴力也可以过 = =。
我用的是BFS，不知道用位运算能不能称作状态压缩 囧。

  1. #include<iostream>
  2. using namespace std;
  3.  
  4. #define N 4
  5. #define DIR 5
  6.  
  7. const int dir[5] = { 0,1,-1,4,-4};
  8.  
  9. int bfs(int s, int e){
  10.         int queue[65536];
  11.         int front = 0, rear = 1;
  12.         queue[0] = s;
  13.         int mz[65536];
  14.         memset(mz, 0, sizeof(mz));
  15.         mz[s] = 1;
  16.         while(front<rear){
  17.                 int x = queue[front];
  18.                 if(x==e)return mz[x]-1;
  19.                 for(int i=0; i<N*N; i++){
  20.                         int t = x;
  21.                         for(int j=0; j<DIR; j++){
  22.                                 int y = i + dir[j];
  23.                                 if(j==1&&y%4==0)continue;
  24.                                 if(j==2&&y%4==N-1)continue;
  25.                                 if(y>=0&&y<N*N){
  26.                                         t^=1<<y;
  27.                                 }
  28.                         }
  29.                         if(mz[t]==0){
  30.                                 mz[t] = mz[x]+1;
  31.                                 queue[rear++] = t;
  32.                         }
  33.                 }
  34.                 front++;
  35.         }
  36.         return -1;
  37. }
  38.  
  39. int main(){
  40.         int k;
  41.         cin>>k;
  42.         while(k--){
  43.                 int s,e,i,j,x;
  44.                 s = e = 0;
  45.                 for(i=0; i<N; i++){
  46.                         for(j=0; j<N; j++){
  47.                                 cin>>x;
  48.                                 s += x<<(i*4+j);
  49.                         }
  50.                 }
  51.                 for(i=0; i<N; i++){
  52.                         for(j=0; j<N; j++){
  53.                                 cin>>x;
  54.                                 e += x<<(i*4+j);
  55.                         }
  56.                 }
  57.                 cout<<bfs(s,e)<<endl;
  58.         }
  59.         return 0;
  60. }

 

  • 无匹配
Small_feed 评论 (0)

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter