【Summarize】

　　1.划分为两堆的无序模型可以利用二进制枚举，

　　而划分为两堆的有序模型可以枚举全排列取定长

　　2.当搜索终态唯一时可考虑逆向搜索

 

POJ 1979：Red and Black

/*    一个矩形的屋子里有一个人，他可以踩黑格子，但是不能踩红格子，    他现在站在一个黑格子上，告诉你房间的布局，    这个人可以向上下左右四个方向移动，问这个人最多能到达的格子数*/#include 
     
      #include 
      
       using namespace std;int W,H,ans,vis[35][35];char mp[35][35];const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};bool check(int x,int y){    if(vis[x][y])return 0;    if(mp[x][y]=='.'&&x&&y&&x<=H&&y<=W)return 1;    return 0;}void dfs(int x,int y){    vis[x][y]=1;ans++;    for(int i=0;i<4;i++){        if(check(x+dx[i],y+dy[i]))dfs(x+dx[i],y+dy[i]);    }return;}int main(){    while(~scanf("%d%d",&W,&H),W+H){        ans=0; memset(vis,0,sizeof(vis));        for(int i=1;i<=H;i++)scanf("%s",mp[i]+1);        for(int i=1;i<=H;i++)for(int j=1;j<=W;j++)        if(mp[i][j]=='@')dfs(i,j);        printf("%d\n",ans);    }return 0;}
      
     

AOJ 0118：Property Distribution

/*    颜色相同且相邻的块属于同一个果园，求果园的总个数*/#include 
     
      #include 
      
       using namespace std;int W,H,ans,vis[105][105];char mp[105][105];const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};bool check(int x,int y,char c){    if(vis[x][y])return 0;    if(mp[x][y]==c&&x&&y&&x<=H&&y<=W)return 1;    return 0;}void dfs(int x,int y,char c){    vis[x][y]=1;    for(int i=0;i<4;i++){        if(check(x+dx[i],y+dy[i],c))dfs(x+dx[i],y+dy[i],c);    }return;}int main(){    while(~scanf("%d%d",&H,&W),W+H){        ans=0; memset(vis,0,sizeof(vis));        for(int i=1;i<=H;i++)scanf("%s",mp[i]+1);        for(int i=1;i<=H;i++)for(int j=1;j<=W;j++)        if(!vis[i][j]){ans++;dfs(i,j,mp[i][j]);}        printf("%d\n",ans);    }return 0;}
      
     

AOJ 0033：Ball

/*    给出十个小球排成一列，从两个出口出去，问能否做到将十个球按一定分配，    使得两个出口出来的球标号都是递增*/#include 
     
      int T,a[10];void solve(){    for(int i=0;i<(1<<10);i++){        int pre1=0,pre2=0,flag=1;        for(int j=0;j<10;j++){            if((1<
     

POJ 3009：Curling 2.0

/*    将一块石头从起点滚到终点，一次必须要滚到碰到石头才会停下来，    而碰到的石头会破碎，如果十步内能到终点则输出步数，否则输出无解*/#include 
     
      #include  
      
       using namespace std;int mp[25][25],ans=0,W,H;const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};bool check(int x,int y){    if(mp[x][y]%2==0&&x&&y&&x<=H&&y<=W)return 1;    return 0;}bool in(int x,int y){    if(x&&y&&x<=H&&y<=W)return 1;    return 0;}void dfs(int x,int y,int d){    if(d>=10)return;    for(int i=0;i<4;i++){        int nx=x,ny=y,flag=0;        while(check(nx+dx[i],ny+dy[i])){            nx+=dx[i],ny+=dy[i];flag=1;        }if(in(nx+dx[i],ny+dy[i])){            if(mp[nx+dx[i]][ny+dy[i]]==3){ans=min(ans,d+1);return;}            if(flag){                mp[nx+dx[i]][ny+dy[i]]=0;                dfs(nx,ny,d+1);                mp[nx+dx[i]][ny+dy[i]]=1;            }        }    }}int main(){    while(~scanf("%d%d",&W,&H),W+H){        ans=11;        for(int i=1;i<=H;i++){            for(int j=1;j<=W;j++){                scanf("%d",&mp[i][j]);            }        }        for(int i=1;i<=H;i++){            for(int j=1;j<=W;j++){                if(mp[i][j]==2)dfs(i,j,0);            }        }if(ans>10)puts("-1");        else printf("%d\n",ans);    }return 0;}
      
     

AOJ 0558：Cheese

/*    求从起点开始依次到1，2，……，N，的总距离的最小值*/#include 
     
      #include 
      
        #include 
       
        using namespace std;const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};int W,H,T,ans=0,v[1005][1050];char mp[1005][1005];struct data{int x,y;}st,en,P[15];bool check(data x){    return(x.x&&x.y&&x.x<=H&&x.y<=W&&mp[x.x][x.y]!='X'&&v[x.x][x.y]==-1);}int bfs(data st,data en){    queue
         Q;    data nx;    for(int i=1;i<=H;i++)        for(int j=1;j<=W;j++)v[i][j]=-1;    Q.push(st);     v[st.x][st.y]=0;    while(Q.size()){        data px=Q.front();        Q.pop();        if(px.x==en.x&&px.y==en.y)break;        for(int i=0;i<4;i++){            nx.x=px.x+dx[i];            nx.y=px.y+dy[i];            if(check(nx)){                Q.push(nx);                v[nx.x][nx.y]=v[px.x][px.y]+1;            }        }        }return v[en.x][en.y];}int main(){    scanf("%d%d%d",&H,&W,&T);    for(int i=1;i<=H;i++)scanf("%s",mp[i]+1);    for(int i=1;i<=H;i++)for(int j=1;j<=W;j++){        if(mp[i][j]<='9'&&mp[i][j]>='1'){            int c=mp[i][j]-'0';            P[c].x=i;P[c].y=j;        }else if(mp[i][j]=='S'){            st.x=i;st.y=j;        }    }    for(int i=1;i<=T;i++){        en.x=P[i].x;en.y=P[i].y;        ans+=bfs(st,en);        st.x=en.x;st.y=en.y;    }printf("%d\n",ans);    return 0;}
       
      
     

POJ 3669：Meteor Shower

/*    告诉你流星砸下来的时间和砸的位置，每次流星砸下来会影响周边五个格子    被影响到的地方将不能再通行，问能到达安全地点的最短时间*/#include 
     
      #include 
      
       #include 
       
        using namespace std;const int N=305,inf=INT_MAX; int t,h,n,mp[N][N],vis[N][N],x,y,tim;int mx[4]={0,0,1,-1},my[4]={1,-1,0,0};struct data{int x,y,t;}q[N*N];void bfs(){    vis[0][0]=t=h=1;    if(mp[0][0]==inf){puts("0");return;}    while(t<=h){        x=q[t].x,y=q[t].y,tim=q[t++].t;        for(int i=0;i<4;i++){            int nx=x+mx[i],ny=y+my[i];            if(nx<0||ny<0||vis[nx][ny]||tim+1>=mp[nx][ny])continue;            if(mp[nx][ny]==inf){printf("%d\n",tim+1);return;}            q[++h].x=nx;q[h].y=ny;q[h].t=tim+1;vis[nx][ny]=1;        }    }puts("-1");}int main(){    for(int i=0;i
       
      
     

AOJ 0121：Seven Puzzle

/*    七数码问题，将标号1到7的块通过向空位的移动来复原    由于操作可逆，直接通过从终态开始搜索的方法，    将到达每种状态需要的时间记录下来*/#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
        
       
      
     

POJ 2718：Smallest Difference

/*    给出不重复的数位，将其全部用上组成两个数，使得其差最小，    输出这个最小差值*/#include 
     
      #include 
      
       #include 
       
        using namespace std;int a[10],n,T;char c;int main(){    scanf("%d",&T);getchar();    while(T--){        for(n=0;(c=getchar())!='\n';)if(c!=' ')a[n++]=c-'0';        if(n==1)printf("%d\n",a[0]);        else if(n==2)printf("%d\n",abs(a[1]-a[0]));        else{            while(a[0]==0)next_permutation(a,a+n);              int ans=INT_MAX,mid=(n+1)>>1;              do{                  if(a[mid]){                      int x=a[0],y=a[mid];                      for(int i=1;i
        
         abs(x-y))ans=abs(x-y);                  }              }while(next_permutation(a,a+n));              printf("%d\n",ans);          }    }return 0;}
        
       
      
     

POJ 3187：Backward Digit Sums

/*    求一个排列使得其不断地进行邻项相加，最后得到的数为给出的数字*/#include 
     
      #include 
      
       using namespace std;int a[10],b[10],n,s;int main(){    scanf("%d%d",&n,&s);    for(int i=0;i
      
     

AOJ 0525：Osenbei

/*    可以翻转行或者列，使得最终状态1最多*/#include 
     
      #include 
      
       #include 
       
        using namespace std;int R,C,b,ans;bitset<10000> a[10];bool tmp;void dfs(int k){    if(k==R){        int tmp=0;        for(int j=0;j
       
      
     

POJ 3050：Hopscotch

/*    求在图中任选起点随意走六步能产生的不同的序列的个数*/#include 
     
      #include 
      
       using namespace std;const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};int mp[1000000],a[6][6],ans=0;int check(int x,int y){return(x&&y&&x<6&&y<6);}void dfs(int x,int y,int d,int num){    if(d==6){if(!mp[num]){mp[num]=1;ans++;}return;}    num=num*10+a[x][y];    for(int i=0;i<4;i++){        int nx=x+dx[i],ny=y+dy[i];        if(check(nx,ny))dfs(nx,ny,d+1,num);    }}int main(){    for(int i=1;i<=5;i++)for(int j=1;j<=5;j++)scanf("%d",&a[i][j]);    for(int i=1;i<=5;i++)for(int j=1;j<=5;j++)dfs(i,j,0,0);    printf("%d\n",ans);    return 0;}