八数码问题（广搜）noj

Picture1

Picture2

Picture3

Picture4

Picture5

#include<iostream>
#include<queue>
#include<map>
#define true 1
#define false 0
using namespace std;

int b[3][3];
int num=0;
int dir[4][2]={
    0,1,//右
    0,-1,//左
    1,0,//下
    -1,0//上
};
queue<int>q1;
map<int,int>smap;

void input();
void init();
int bfs();
int canMoveTo(int now,int k);
int moveTo(int now,int k);
int isTarget(int next);

int main()
{
    input();
    init();
    cout<<bfs()<<endl;
    return 0;
}
void input()
{
    int i,j;
    for(i=0;i<3;i++){
        for(j=0;j<3;j++){
            cin>>b[i][j];
            num=num*10+b[i][j];
        }
    }
}
void init()
{
    q1.push(num);
    smap[num]=0;
}
int bfs()
{
    int now,next;
    int i;
    while(!q1.empty()){
        now=q1.front();
        q1.pop();
        for(i=0;i<4;i++){
            if(canMoveTo(now,i)){
                next=moveTo(now,i);
                if(isTarget(next))return smap[now]+1;
                if(smap.count(next)==0){
                    q1.push(next);
                    smap[next]=smap[now]+1;
                }
            }
        }
    }
    return -1;
}
int canMoveTo(int now,int k)
{
    int a[3][3];
    int i,j,tmp;
    int flag=1;
    int row,col;
    for(i=2;i>=0&&flag==1;i--){
        for(j=2;j>=0;j--){
            tmp=now%10;
            now=now/10;
            a[i][j]=tmp;
            if(a[i][j]==0){
                flag=0;
                row=i;
                col=j;
                break;
            }
        }
    }
    row=row+dir[k][0];
    col=col+dir[k][1];
    if(row>=0&&row<3&&col>=0&&col<3)return true;
    else return false;
}
int moveTo(int now,int k)
{
    int i,j;
    int tmp;
    int row,col;
    int rrow,ccol;
    for(i=2;i>=0;i--){
        for(j=2;j>=0;j--){
            tmp=now%10;
            now=now/10;
            b[i][j]=tmp;
            if(b[i][j]==0){
                row=i;
                col=j;
            }
        }
    }
    rrow=row+dir[k][0];
    ccol=col+dir[k][1];
    b[row][col]=b[rrow][ccol];
    b[rrow][ccol]=0;
    tmp=0;
    for(i=0;i<3;i++){
        for(j=0;j<3;j++){
            tmp=tmp*10+b[i][j];
        }
    }
    return tmp;
}
int isTarget(int next)
{
    if(next==123456780)return true;
    else return false;
}

注：map.count(Key)返回值为1或者0，1返回存在，0返回不存在，返回的是布尔类型的值，因为在map类型中所有的数据的Key值都是不同的，所以被count的数要么存在1次，要么不存在。