题目描述

要求输入一个拼图的初始状态，返回拼图的成功所经过的最小的步数,例如：

初始状态：1 2 34 5 67 0 8成功的状态1 2 34 5 67 8 0输出步数 ： 1

0号可以与相邻的数字进行交换，要求最后的状态0号位于右下方，其余位置按上面的顺序排列

分析

这和我们常见的迷宫求解的题目有些差别，迷宫求解的过程中可以标记走过的路，以防止重复同样的步骤，但这里不能通过标记走过的位置了，因为一个要达到最终的状态，可能一个位置要重复地走很多遍才能达到成功的状态。

虽然不能标记拼图中单独的位置，我们可以把整个地图的状态保存下来，当0位置改变的时候，我们判断改变后的拼图是否已经出现过，如果出现过，0位置不改变，否则才改变。

这里我们采用递归的分析方式，函数findCount（x,y）返回当0位于（x,y）位置时到达成功状态所经过的最小的步数，每次0号位置都有四种移动方案向上、向下、向左、向右，只要统计出经过四个方向到达成功状态的最小步数，

转换成代码就是

findCount(x,y) = min(findCount(x-1,y),findCount(x,y-1)						, findCount(x+1,y),findCount(x,y+1));

只要找到递归的公式，递归的代码比较容易了。

这里还有一个问题就是怎样保存整个拼图，这个方法有很多，我用了一种hash的方式

//传入保存拼图的数组    int fun(vector
   
    
      > &vec)    {
           int tmp = 0;        int row = vec.size();        for(int i = 0; i < row; ++i)        {
               int col = vec[i].size();            for(int j = 0; j < col; ++j)            {
                   int a = vec[i][j] + (i*row+j);                //求解拼图中各个位加上一定的对应的数值后，再向右移动相应的位数，                //这里要尽量保证不同的拼图状态求出的hash 值不相同                tmp += (a << (i*row+j));            }        }        return tmp;    }

代码的完整实现

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;#define INF 0x3f3f3f//==================================================================================//计算出二维数字的hash 作为当前数组的状态class CHash{
   public:    int fun(vector
       
        
          > &vec) { int tmp = 0; int row = vec.size(); for(int i = 0; i < row; ++i) { int col = vec[i].size(); for(int j = 0; j < col; ++j) { int a = vec[i][j] + (i*row+j); tmp += (a << (i*row+j)); } } return tmp; }};//===================================================================================class Solution{ public: Solution(int row = 2,int col = 3) { //初始化方向 H[0] = 1; V[0] = 0; H[1] = 0; V[1] = -1; H[2] = -1; V[2] = 0; H[3] = 0; V[3] = 1; //初始化_nums;给出一个成功的状态，求出hash值保存，以便比较 int k = 1; for(int i = 0; i < row; ++i) { vector
         
           tmp; for(int j = 0; j < col; ++j) { tmp.push_back(k++); } _nums.push_back(tmp); tmp.clear(); } _nums[row-1][col-1] = 0; //初始化_endStat; _endStat = _hash.fun(_nums); } //交换数组中的两个元素 void swap(int i,int j,int tmpx,int tmpy); //查找最少的次数 int findCount(int x,int y); //设置数组的初始状态 vector
          
            setNums();private: vector
           
            
              > _nums; unordered_map
             
               _map; //保存已经遍历过的状态 //map
              
                _map; //保存已经遍历过的状态 int _endStat; //成功状态; CHash _hash; int H[4]; int V[4];};//移动0后交换两个数值void Solution::swap(int x,int y,int tmpx,int tmpy){ _nums[x][y] = _nums[x][y]^_nums[tmpx][tmpy]; _nums[tmpx][tmpy] = _nums[x][y]^_nums[tmpx][tmpy]; _nums[x][y] = _nums[x][y]^_nums[tmpx][tmpy];}//设置初始化的拼图的值，并返回0的位置vector
               
                 Solution::setNums(){ int row = _nums.size(); int col = _nums[0].size(); vector
                
                  tmp; for(int i = 0; i < row; ++i) { for(int j = 0; j < col; j++) { int data; //键盘终端获取最初的拼图的状态 cin >> data; if(data == 0) { tmp.push_back(i); tmp.push_back(j); } _nums[i][j] = data; } } return tmp;}int Solution::findCount(int x,int y){ if(_hash.fun(_nums) == _endStat) { return 0; } else { int m = INF; for(int i = 0; i < 4; i++) { int tmpx = x+H[i]; int tmpy = y+V[i]; //判断与0交换的位置的合法性 if(tmpx >= 0 && tmpx < _nums.size() && tmpy >= 0 && tmpy < _nums[x].size()) { //交换位置 swap(x,y,tmpx,tmpy); //求交换后的hash值 int hashNums = _hash.fun(_nums); //判断交换后的状态是否出现过 auto it = _map.find(hashNums); //没有出现过则添加 if(it == _map.end()) { _map[hashNums]++; //此时0号位置改变，求改变后最少经过多少步能达到成功状态 //求出count后，count+1就是改变前到达成功状态所经过的步数 int count = findCount(tmpx,tmpy); //如果到不了成功状态，返回值 > INF(前面的宏定义) //m记录的是达到成功状态经过的最少步数， //把一些确定不可能到达目的状态的或者到达目的状态较长的路径剪掉 if(count < m) { it = _map.find(hashNums); _map.erase(it); } //记录四个方向中经过的最少步骤 if(m > count) { m = count; } } //回溯到交换之前的状态，进入下一个方向的选择 swap(x,y,tmpx,tmpy); } } return m+1; //最小步数加一 也就是当前位置的最小步数 }}int main(){ int row,col; cout << "输入拼图的行数和列数:"; cin >> row >> col; Solution s(row,col); vector
                 
                   vec = s.setNums(); cout << s.findCount(vec[0],vec[1]) << endl; return 0;}

如有问题可以在留言板中留言，希望共同学习。

转载地址：http://gtnwi.baihongyu.com/

你可能感兴趣的文章