| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2172 人关注过本帖
标题:求大优化神代码
只看楼主 加入收藏
丨Blue丶
Rank: 1
等 级:新手上路
帖 子:2
专家分:0
注 册:2015-6-19
收藏
 问题点数:0 回复次数:1 
求大优化神代码
九宫问题
一、设计目的  通过实践掌握用广度优先搜索解决问题的方法。
二、问题描述
     在一个3*3的九宫中,有1—8这8个数,及一个空格随机的摆放在其中的格子里。如下面左图所示。要求实现这样的问题:将九宫问题调整为如右图所示的形式。调整的规则是:每次只能将与空格(上、下或左、右)相邻的一个数字平移到空格中。
要求:问你通过移动中间的空格是否能达到右图所示的状态,如果能,则输出所走的路径,如果不能,则输出:unsolvable。最好能画出九宫的图形形式,并在其上动态的演示移动过程。
           
输入:包括多组测试数据,每组输入占一行,每行9个字符,表示矩阵中从左到右,从上到下的方格里的信息。
输出:对于每一组数据,输出一行,表示空格所经过的路径。
#include <stdio.h>
#include <stdlib.h>
#include <windows.h>
#include <queue>
#include <stack>
using namespace std;
#define HashTableSize 362880
#define NOT        !
#define MaxDeep 50
typedef struct maps
{
    int detail[3][3];
    int x, y;            // 记录 空格(0)的坐标
}Map,*PMap;
Map   org;                //  初始状态
Map   end;                //    目标状态

bool  HashTable[HashTableSize]={false};        //hash表
int const derection[4][2] ={ { -1 , 0 }  , {1, 0 }, { 0 , -1 } , { 0, 1 } } ;  // 可移动的四个方向
int   Path[ MaxDeep + 1 ];
int   Step;
bool  Finish;
/**
 *
 *    八数码的输入(在这里不做任何输入检查,均认为输入数据是正确的)
 *
 **/
void input()
{
    int i,j;
    int sum;
    for(i = 0 ; i < 9 ; i ++ )
    {
        scanf("%1d", *org.detail + i );
        if(0 == *(*org.detail + i) )
        {
            org.x = i / 3;
            org.y = i % 3;
        }
    }
    for(i = 0 ; i < 9 ; i ++ )                //计算逆序
    {
        if( 0 == *(*org.detail + i) )  
            continue;

        for(j = 0 ; j < i;  j ++ )
            if( 0 != *(*org.detail+j) && *(*org.detail + j) < *(*org.detail + i) )  
            {
                sum ++;  
            }
    }
    if( sum%2 == 0 )        // 目标状态各个数字对应的坐标位置
    {
        end.detail[0][0] = 1 , end.detail[0][1] = 2 , end.detail[0][2] = 3 ;
        end.detail[1][0] = 4 , end.detail[1][1] = 5 , end.detail[1][2] = 6 ;
        end.detail[2][0] = 7 , end.detail[2][1] = 8 , end.detail[2][2] = 0 ;
    }
    else
    {
        printf("unsolvable");
    }  
}
/**
 *
 *检测两个状态是否一样
 *
 **/
inline bool IsEqual(Map a , Map b)
{
    return 0 == memcmp((const void *)(*a.detail),(const void *)(*b.detail),36);
}
/**
 *
 * hash值的计算
 *
**/
int HashValue(Map a)   
{
   int count  ;  
   int i , j ;
   int value =0 ;
   static int pv[9]={1,1,2,6,24,120,720,5040,40320};
   for(i = 0 ; i < 9 ; i ++ )
   {
       for(j = 0, count =0 ; j < i ; j ++ )
       {
            if( *(*a.detail+i) < *(*a.detail+j) )  
            {
                count ++;
            }
       }
       value += pv[i]*count;
   }
    return value;
}
/**
 *
 *   深度优先搜索
 *
 **/
void Dfs(Map& node , int deep )
{
    if(deep > MaxDeep )  
        return ;
    if( true == IsEqual( node , end) )
    {
        Finish = true;
        Step = deep;
        return ;
    }
    for(int k =0 ;k  < 4 && NOT Finish ; k ++ )
    {
        Map tmp = node ;  
        tmp.x = node.x + derection[k][0],
        tmp.y = node.y + derection[k][1];
        if(tmp.x < 0 || tmp.x > 2 || tmp.y <0 || tmp.y >2 )  
        {
            continue;
        }
        tmp.detail[ node.x ][ node.y ] = tmp.detail[ tmp.x ][ tmp.y ];        //移动空格
        tmp.detail[ tmp.x ][ tmp.y ] = 0 ;

        int tmpindex = HashValue( tmp );
        if(HashTable[ tmpindex ] == true )
            continue;
        HashTable[ tmpindex ] = true;
        Path[ deep ] = k ;  
        Dfs( tmp , deep + 1) ;  
        HashTable[ tmpindex ] = false;
    }
    return ;
}
/**
 *
 *    输出 结果
 *
 **/
void output()
{
    Map now = org ;
    int oldx,oldy;
    int count =0 ;  
    printf("共需要 %d 步.\n", Step);
    for(int i =0 ; i < 3; i ++ )
    {
        for(int j =0 ; j < 3; j  ++)
        {
            printf("%3d",org.detail[ i ][ j ]);
        }
        printf("\n");
    }
    for( int k =0 ; k < Step ; k ++ )
    {
        oldx = now.x , oldy = now.y ;  
        now.x += derection[ Path[ k ] ][ 0 ], now.y += derection[ Path[ k ] ][ 1 ];

        now.detail[ oldx ][ oldy ] = now.detail[ now.x ][ now.y ];        //移动空格
        now.detail[ now.x ][ now.y ] = 0 ;         
        printf("\n    ↓ 第%d步\n",++count);
        getchar();
        for(int i =0 ; i < 3; i ++ )
        {
            for(int j =0 ; j < 3; j  ++)
            {
                printf("%3d",now.detail[ i ][ j ]);
            }
            printf("\n");
        }
    }
    printf("\nThe End!\n");  
}
int main()
{
    input();
    long time =GetTickCount();
    HashTable[ HashValue( org ) ] = true;
    Dfs( org , 0 );
    printf("计算用时:%dMS\n",GetTickCount()-time);
    output();
    return 0;
}

代码如上,动态演示和九宫图形样式不会添加。

[ 本帖最后由 丨Blue丶 于 2015-6-26 09:23 编辑 ]
2015-06-19 09:24
丨Blue丶
Rank: 1
等 级:新手上路
帖 子:2
专家分:0
注 册:2015-6-19
收藏
得分:0 
2015-06-22 16:21
快速回复:求大优化神代码
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.015511 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved