【BFS】bzoj1054[HAOI2008]移动玩具

 1 #include
 2 #include
 3 #include<set>
 4 #include
 5 using namespace std;
 6 const int di[]={0,0,-1,1},dj[]={-1,1,0,0};
 7 struct Squ{char S[4][4];};
 8 struct Node{Squ v;int d;Node(const Squ &a,const int &b){v=a;d=b;}Node(){}};
 9 bool operator <(const Squ &a,const Squ &b)
10 {
11     for(int i=0;i<4;i++)
12       for(int j=0;j<4;j++)
13         if(a.S[i][j]<b.S[i][j])
14           return true;
15         else if(a.S[i][j]>b.S[i][j])
16           return false;
17     return false;
18 }
19 bool operator == (const Squ &a,const Squ &b)
20 {
21     for(int i=0;i<4;i++)
22       for(int j=0;j<4;j++)
23         if(a.S[i][j]!=b.S[i][j])
24           return false;
25     return true;
26 }
27 Squ from,to;
28 setSet;
29 queueq;
30 inline bool check(const int &x,const int &y)
31 {
32     if(x>=0&&x<4&&y>=0&&y<4&&q.front().v.S[x][y]=='0')
33       return true;
34     return false;
35 }
36 inline void work(const Squ &tmp)
37 {
38     if(Set.find(tmp)==Set.end())
39       {
40           if(tmp==to)
41             {
42                 printf("%d\n",q.front().d+1);
43                 exit(0);
44             }
45           Set.insert(tmp);
46           q.push(Node(tmp,q.front().d+1));
47       }
48 }
49 int main()
50 {
51     for(int i=0;i<4;i++)scanf("%s",from.S[i]);
52     for(int i=0;i<4;i++)scanf("%s",to.S[i]);
53     if(from==to){printf("0\n");return 0;}
54     q.push(Node(from,0));
55     Set.insert(from);
56     while(!q.empty())
57       {
58           for(int i=0;i<4;i++)
59             for(int j=0;j<4;j++)
60               if(q.front().v.S[i][j]=='1')
61                 {
62                     for(int k=0;k<4;k++)
63                       {
64                           int ti=i+di[k],tj=j+dj[k];
65                           if(check(ti,tj))
66                             {
67                                 Squ tmp=q.front().v;
68                                 swap(tmp.S[i][j],tmp.S[ti][tj]);
69                                 work(tmp);
70                             }
71                       }
72                 }
73           q.pop();
74       }
75     return 0;
76 }