一个有趣的算法,实现色块的交换,怎么实现呢

iShown 发布于 2016/02/02 12:41
阅读 502
收藏 0
There're 7 red tiles, 8 blue titles and one white title in a 4 x 4 plane. We could only move the white tile. When moving it, the white tile swaps the position with the adjacent tile. L, R, U, D are corresponding to four directions which the tile could be moved to (Left, Right, Up, Down) For example, starting from configuration (S), by the move sequence RDRDL we reach the configuration (E). Now, starting from configuration (S), find the shortest way to reach configuration (T).


(S)

        

(E)

        

(T)


What is the move sequence of the path ?
加载中
0
htfy96
htfy96
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <vector>
using namespace std;
typedef long state;
//状态压缩,低0~15位:0代表红块或者空格,1代表蓝块
//16~17位:空格x,18~19:空格y

const int dx[]={0,0,1,-1};
const int dy[]={1,-1,0,0};

inline int getX(state s)
{
    return (s & ((1<<16) + (1<<17)))>>16;
}

inline int getY(state s)
{
    return (s & ((1<<18) + (1<<19)))>>18;
}

int d[1<<20]; //从初始状态到需要多少步
state last[1<<20];//上一步状态是多少

inline bool legal(int x, int y)
{
    return x>=0 && x<4 && y>=0 && y<4;
}

inline state xy2bit(int x, int y)
{
    return ((x<<2) + y);
}

inline int getBit(state s, state bit)
{
    bit = 1<<bit;
    return (s & bit) >0 ;
}

state change(state olds, int pdx, int pdy) //给定当前状态和移动的方向,求下一个状态
{
    int oldx = getX(olds), oldy = getY(olds);
    olds = (olds & 0xffff) + ((oldx + pdx)<<16) + ((oldy+pdy)<<18);
    int w = getBit(olds, xy2bit(oldx, oldy)), ww = getBit(olds, xy2bit(oldx+pdx, oldy+pdy));
    olds -= (w* (1<<xy2bit(oldx, oldy)) + ww*(1<<xy2bit(oldx+pdx, oldy+pdy)));
    olds += (ww* (1<<xy2bit(oldx, oldy)) + w*(1<<xy2bit(oldx+pdx, oldy+pdy)));
    return olds;
}


void search(state s)
{
    int x=getX(s), y=getY(s);
    for (int i=0; i<4; ++i)
      if (legal(x+dx[i], y+dy[i]))
      {
          int news = change(s, dx[i], dy[i]);
          if (d[news] == d[0])
          {
              last[news] = s;
              d[news] = d[s] + 1;
              search(news);
          }
      }
}
          
vector<pair<int,int> > result;
int main()
{
    memset(d, 0x3f, sizeof(d)); // 0x3f3f3f3f: 一个正大数
    d[0xcccc] = 0; //0000 1100 1100 1100 1100 初始状态
    search(0xcccc); 
    cout << d[0x5a5a] << endl; // 0000 0101 1010 0101 1010
    int s = 0x5a5a;
    do
    {
        result.push_back(make_pair(getX(s), getY(s)));
        s = last[s];
    } while (d[s] > 0);
    result.push_back(make_pair(0, 0));
    for (size_t i=0; i<result.size(); ++i)
    {
        int index = result.size() - 1 -i;
      cout << i <<".\t" << result[index].first << " "<< result[index].second << endl;
    }
    
}



0
iShown
iShown
有点明白你的思路,但是写的看不懂,唉,水平有限
0
bobdog1986
bobdog1986
你这是让别人帮你做题啊
iShown
iShown
么得,开阔下思路,学习下大神
返回顶部
顶部