poj 1077 Eight（bfs，dbfs, A*）-白红宇

poj 1077 Eight（bfs，dbfs, A*）

阅读量：6231 次

发布时间：2019-06-21

本文共 6853 字，大约阅读时间需要 22 分钟。

代码如下：

bfs:

1 #include 
     
       2 #include 
       3 #include 
       
         4 #include 
        
          5 #include 
         
           6 using namespace std; 7 typedef long long LL; 8  9 int eight[3][3], xx, xy, dx[]={
   0,0,-1,1,0}, dy[]={
   0,1,0,0,-1};10 char dir[] = "orudl";11 LL tar;12 13 LL encode(){14     LL s=eight[2][2];15     for(int i=7; i>=0; --i){16         s <<=4;17         s |= eight[i/3][i%3];18     }19     return s;20 }21 void decode(LL s){22     for(int i=0; i<9; ++i){23         eight[i/3][i%3] = s%16;24         if(s%16 == 0) 25             xx = i/3, xy = i%3;26         s >>=4;27     }28 }29 queue
          
            que;30 map
           
            
              > mp;// pair:d,ps31 32 void print(LL s){33 int d = mp[tar].first;34 LL ts=s;35 string ope;36 while(d!=-1){37 ope.push_back(dir[d]);38 ts = mp[ts].second;39 d = mp[ts].first;40 }41 reverse(ope.begin(), ope.end());42 cout<< ope<< "\n";43 }44 void bfs(){45 mp.clear();46 LL s = encode(), s2;47 que.push(s); mp[s] = make_pair(-1,0);48 while(!que.empty()){49 s = que.front(); que.pop();50 for(int i=1; i<5; ++i){51 decode(s);52 int r,c;53 r = xx+dx[i], c = xy+dy[i];54 if(r<0 || c<0 || r==3 || c==3)55 continue;56 swap(eight[xx][xy], eight[r][c]);57 s2 = encode();58 if(mp.find(s2)!=mp.end())59 continue;60 mp[s2] = make_pair(i,s);61 if(s2==tar){62 print(s2);63 return ;64 }65 else que.push(s2);66 }67 }68 }69 int main(){70 std::ios::sync_with_stdio(false);71 char c;72 for(int i=0; i<3; ++i){73 for(int j=0; j<3; ++j){74 cin>>c;75 if(c=='x')76 eight[i][j]=0, xx = i, xy = j;77 else 78 eight[i][j]= c-'0';79 }80 }81 tar=8;82 for(int i=7; i>0; --i)83 tar<<=4, tar |= i;84 int cnt=0; 85 for(int i=0; i<9; ++i){86 for(int pi=0; pi

dbfs：

1 #include 
      
         2 #include 
         3 #include 
        
           4 #include 
         
            5 #include 
          
             6 using namespace std;  7 typedef long long LL;  8   9 int eight[3][3], xx, xy, dx[]={
    0,0,-1,1,0}, dy[]={
    0,1,0,0,-1}; 10 char dir[] = "orudl"; 11  12 LL encode(){ 13     LL s=eight[2][2]; 14     for(int i=7; i>=0; --i){ 15         s <<=4; 16         s |= eight[i/3][i%3]; 17     } 18     return s; 19 } 20 void decode(LL s){ 21     for(int i=0; i<9; ++i){ 22         eight[i/3][i%3] = s%16; 23         if(s%16 == 0)  24             xx = i/3, xy = i%3; 25         s >>=4; 26     } 27 } 28 queue
           
             que[2]; 29 map
            
             
               > mp[2];// pair:d,ps 30 31 void print(LL s){ 32 int d = mp[0][s].first; 33 LL ts=s; 34 string ope; 35 while(d!=-1){ 36 ope.push_back(dir[d]); 37 ts = mp[0][ts].second; 38 d = mp[0][ts].first; 39 } 40 reverse(ope.begin(), ope.end()); 41 cout<< ope; 42 ope.clear(), d = mp[1][s].first, ts = s; 43 while(d!=-1){ 44 ope.push_back(dir[d]); 45 ts = mp[1][ts].second; 46 d = mp[1][ts].first; 47 } 48 cout << ope << "\n"; 49 } 50 void expand(int idx){ 51 static int found = 0; 52 if(found){ 53 while(!que[idx].empty()) que[idx].pop(); 54 return; 55 } 56 int len = que[idx].size(); 57 while(len--){ 58 LL s = que[idx].front(), s2; que[idx].pop(); 59 for(int i=1; i<5; ++i){ 60 decode(s); 61 int r,c; 62 if(idx==0) 63 r = xx+dx[i], c = xy+dy[i]; 64 else 65 r = xx-dx[i], c = xy-dy[i]; 66 if(r<0 || c<0 || r==3 || c==3) 67 continue; 68 swap(eight[xx][xy], eight[r][c]); 69 s2 = encode(); 70 if(mp[idx].find(s2)!=mp[idx].end()) 71 continue; 72 mp[idx][s2] = make_pair(i,s); 73 if(mp[idx^1].find(s2)!=mp[idx^1].end()){ 74 print(s2); 75 found=1; 76 return ; 77 } 78 else que[idx].push(s2); 79 } 80 } 81 } 82 void dbfs(){ 83 mp[0].clear(), mp[1].clear(); 84 LL tar=8; 85 for(int i=7; i>0; --i) 86 tar<<=4, tar |= i; 87 que[1].push(tar); mp[1][tar]=make_pair(-1,0);// 两者相等?? 88 tar = encode(); 89 que[0].push(tar); mp[0][tar] = make_pair(-1,0); 90 while(!que[0].empty() && !que[1].empty()){ 91 if(que[0].size()
              
               >c;107 if(c=='x')108 eight[i][j]=0, xx = i, xy = j;109 else 110 eight[i][j]= c-'0';111 }112 }113 int cnt=0; 114 for(int i=0; i<9; ++i){115 for(int pi=0; pi

View Code

A*:

1 #include 
      
         2 #include 
         3 #include 
        
           4 #include 
         
            5 #include 
          
             6 #include 
           
             7 using namespace std; 8 typedef long long LL; 9 10 int eight[3][3], xx, xy, dx[]={ 0,-1,1,0}, dy[]={ 1,0,0,-1}; 11 char dir[] = "rudl"; 12 LL init, tar; 13 14 LL encode(){ 15 LL s=eight[2][2]; 16 for(int i=7; i>=0; --i){ 17 s <<=4; 18 s |= eight[i/3][i%3]; 19 } 20 return s; 21 } 22 void decode(LL s){ 23 for(int i=0; i<9; ++i){ 24 eight[i/3][i%3] = s%16; 25 if(s%16 == 0) 26 xx = i/3, xy = i%3; 27 s >>=4; 28 } 29 } 30 class Node { 31 public: 32 LL s, ps; 33 int f,g,h,d; 34 Node (LL _s=0, LL _ps=0, int _d=-1, int _f=0, int _g=0, int _h=0){ 35 s = _s, ps = _ps, f = _f, g = _g, h = _h, d = _d; 36 } 37 int operator<(const Node & b) const { 38 return this->f < b.f || (this->f==b.f && this->s
            
              closed, open; 43 map
             
              ::iterator> inOpen, inClosed; 44 45 void print(Node nd){ 46 int d = nd.d; 47 LL ts = nd.s; 48 string ope; 49 while(d!=-1){ 50 ope.push_back(dir[d]); 51 auto itc = inClosed[nd.ps]; 52 nd = *itc; 53 d = nd.d; 54 } 55 reverse(ope.begin(), ope.end()); 56 cout<< ope<< "\n"; 57 } 58 int hn(LL s){ 59 decode(s); 60 int cnt=0; 61 for(int i=0; i<9; ++i){ 62 if(eight[i/3][i%3] != (i+1)%9) cnt++; 63 } 64 return cnt; 65 } 66 void astar(){ 67 init = encode(); 68 int inith = hn(init); 69 Node start = Node(init, 0, -1, inith, 0, inith); 70 open.insert(start); 71 while(!open.empty()){ 72 Node tn = *open.begin(); inOpen.erase(tn.s); open.erase(tn); 73 LL ts = tn.s, s2; 74 int tf = tn.f, tg = tn.g, th = tn.h; 75 for(int i=0; i<4; ++i){ 76 decode(ts); 77 int r = xx+dx[i], c=xy+dy[i]; 78 if(r<0 || c<0 || r==3 || c==3) continue; 79 swap(eight[r][c], eight[xx][xy]); 80 s2 = encode(); 81 int g = tg+1, h = hn(s2), f = g+h; 82 Node nd = Node(s2, ts, i, f, g, h); 83 if(s2 == tar){ 84 inClosed[tn.s]= closed.insert(tn); 85 inClosed[nd.s]= closed.insert(nd); 86 print(nd); 87 return; 88 } 89 auto ito = inOpen.find(s2), itc = inClosed.find(s2); 90 if(ito == inOpen.end() && itc == inClosed.end()){ 91 inOpen[nd.s]=open.insert(nd); 92 } 93 else if(ito == inOpen.end() && f < itc->second->f){ 94 closed.erase(itc->second); inClosed.erase(itc); 95 inOpen[nd.s]=open.insert(nd); 96 } 97 else if(itc == inClosed.end() && f < ito->second->f){ 98 // que 里有相同s不同f的node 99 open.erase(ito->second), inOpen[nd.s]=open.insert(nd);100 }101 }102 inClosed[tn.s] = closed.insert(tn);103 }104 }105 int main(){106 std::ios::sync_with_stdio(false);107 char c;108 for(int i=0; i<3; ++i){109 for(int j=0; j<3; ++j){110 cin>>c;111 if(c=='x')112 eight[i][j]=0, xx = i, xy = j;113 else 114 eight[i][j]= c-'0';115 }116 }117 tar=8;118 for(int i=7; i>0; --i)119 tar<<=4, tar |= i;120 int cnt=0; 121 for(int i=0; i<9; ++i){122 for(int pi=0; pi