Created
February 15, 2014 15:02
-
-
Save ProgramCaiCai/9020404 to your computer and use it in GitHub Desktop.
aiplan_pa1_astar
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <iostream> | |
| #include <stdio.h> | |
| #include <string.h> | |
| #include <algorithm> | |
| #include <queue> | |
| #include <cmath> | |
| #include <map> | |
| using namespace std; | |
| const int dx[]={0,0,1,-1}; | |
| const int dy[]={1,-1,0,0}; | |
| struct Stat{ | |
| int a[9]; | |
| int zeropos() const{ | |
| for(int i=0;i<9;i++) if(a[i]==0) return i; | |
| } | |
| int h() const { | |
| int ret = 0; | |
| for(int i=0;i<9;i++) { | |
| int x = i/3; | |
| int y = i%3; | |
| int ox = a[i]/3; | |
| int oy = a[i]%3; | |
| ret += abs(x-ox) + abs(y-oy); | |
| } | |
| return ret; | |
| } | |
| bool canmakemove(int dir) const{ | |
| int zp = zeropos(); | |
| int x = zp/3; | |
| int y = zp%3; | |
| x+=dx[dir]; | |
| y+=dy[dir]; | |
| return x>=0 && x<3 && y>=0 && y<3; | |
| } | |
| Stat makemove(int dir) const{ | |
| int zp = zeropos(); | |
| int x = zp/3; | |
| int y = zp%3; | |
| x+=dx[dir]; | |
| y+=dy[dir]; | |
| Stat ret; | |
| for(int i=0;i<9;i++) ret.a[i]=a[i]; | |
| swap(ret.a[zp],ret.a[x*3+y]); | |
| return ret; | |
| } | |
| bool operator<(const Stat &b) const { | |
| for(int i=0;i<9;i++) if(a[i]!=b.a[i]) return a[i]<b.a[i]; | |
| return false; | |
| } | |
| void print() { | |
| printf("["); | |
| for(int i=0;i<9;i++) printf(" %d",a[i]); | |
| printf("]\n"); | |
| } | |
| }; | |
| typedef pair<int,Stat> PIS; | |
| priority_queue<PIS,vector<PIS>,greater<PIS> > pq; | |
| map<Stat,int> mp; | |
| int astar(Stat start){ | |
| while(!pq.empty()) pq.pop(); | |
| mp.clear(); | |
| pq.push(PIS(start.h(),start)); | |
| mp[start]=0; | |
| while(!pq.empty()){ | |
| PIS pis = pq.top(); | |
| pq.pop(); | |
| Stat s = pis.second; | |
| if(s.h()==0) { | |
| return mp[s]; | |
| } | |
| //s.print(); | |
| //printf("%d\n",mp[s]); | |
| for(int i=0;i<4;i++) if(s.canmakemove(i)){ | |
| Stat ns = s.makemove(i); | |
| if((mp.find(ns)== mp.end()) || mp[s]+1<mp[ns]) { | |
| mp[ns]=mp[s]+1; | |
| pq.push(PIS(ns.h()+mp[ns],ns)); | |
| } | |
| } | |
| } | |
| return 10000; | |
| } | |
| queue<Stat> q; | |
| int countbfs(Stat s,int dep=27){ | |
| while(!q.empty()) q.pop(); | |
| q.push(s); | |
| mp.clear(); | |
| mp[s]=0; | |
| int cnt=0; | |
| while(!q.empty()){ | |
| Stat s= q.front(); | |
| q.pop(); | |
| for(int i=0;i<4;i++) if(s.canmakemove(i)){ | |
| Stat ns = s.makemove(i); | |
| if((mp.find(ns)== mp.end())){ | |
| mp[ns]=mp[s]+1; | |
| if(mp[ns]==dep) cnt++; | |
| if(mp[ns]>dep) return cnt; | |
| q.push(ns); | |
| } | |
| } | |
| } | |
| return cnt; | |
| } | |
| Stat start; | |
| int main() | |
| { | |
| cout<<"Input start state: eg. [1 6 4 8 7 0 3 2 5] (without parentheses)"<<endl; | |
| for(int i=0;i<9;i++) cin>>start.a[i]; | |
| //cout<<astar(start)<<endl; | |
| cout<<countbfs(start)<<endl; | |
| return 0; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment