• 这道题目很靠内功!深呼吸,看我怎么搞定你!对了去找个judge online的地方!
  • 昨晚整理思路到很晚,没时间写到blog上了,今天整理了,然后好编码。有两个思路,第一是用纯的搜索来做,书上写的是搜索的极限[我不晓得速度到底会多慢!];第二是基于状态压缩的动态规划,其实主要是限制条件的完备性比较难证明,至于状态压缩和连通性判断,和以往都是一样的。
  • 对于搜索做法,框架明显是路径查找的DFS,主要是两个剪刀比较重要:[注意题目上:Betsy takes her tour of the township going from Farm to Market by walking through every plot exactly once. ]

1,那对于每一个独立的plot[betsy不在附近的四个方向的],至少有一个方向进入,一个方向走出。注意标注的部分:既然我们是假设有一个方向流入,再假设betsy已经占据了一个方向,那么在统计plot的剩余方向时,就要把betsy当前的方向加到plot里面去,这会造成统计的逻辑变难,因此在实现时,只考虑betsy不在附近四个方向上的情况。

编码实现:假设betsy从dir方向进入(Nx,Ny),那么她就不在(x,y)上了,OK,我们check此时的left(x,y)就正好是上述条件!

2.对于第二个剪刀条件,可以简称为“四连通性”,直上直下。等价于,1,betsy不能进入一个有进而无法踏完的区域,进而绕过“自己设置的屏障”,进入另一侧,更确切地说,betsy的当前路径假如把剩余的路径一分为二,那么她在走完一边后[可以反证,从“非边界”部分进入的一侧区域,她是无法踏完的],必须绕过屏障再进入另一侧。这与题设矛盾;2,betsy的路径如果出现“对角”区域,实际上也是一种等价的“自己设置的屏障”,存在两种镜像情况。

我的理解:其实这两种情况都是一致的,只是一种是“直线屏障”,另一种则是“曲线屏障”。

编码实现:判断d1,d2方向即可,只是书上《实用算法》表述有所错误!黑书上还提到一种剪刀,当到达第二列,倒数第二行时,假如左边和下边的格子没有到达,那么也就无法到达。仔细想下,为什么作者能提出这种表述?难道是神来之笔?其实不是的,对于第二种剪刀的下对称镜像,我们怎么分析?d1或d2方向是一定是一个踏过的区域,一个未踏过的区域么?假如其中一个是终点,怎么样?换句话说,与终点形成“对角”区域的也要剪刀!

d1,d2方向增量示意:

 

写这些东西,本菜是要提醒自己,分析的时候要考虑到完备性!不能光想当然![编码下午实现]

测试结果:8的时候,已经慢到754.32s了!看来不用黑书的方法是没法优化的了,先研究下!

#include <iostream>
#include <fstream>

using namespace std;
const int MAXEL=10, MAXDIR=4, LR=2;//max is 100
char map[MAXEL][MAXEL], lef[MAXEL][MAXEL];
char fd[MAXDIR][LR]={{-1,0},/*0*/{0,-1},/*1*/{1,0}/*2*/,{0,1}/*3*/};//x,y
int n,s,size;//Matrix WIDTH, s best path

//DFS path search
void init();
void expand(int step, int x, int y);//x*n+y;
bool cut1(int dir, int x, int y);
bool cut2(int dir, int x, int y);

//implementation
void init(){
    //map clear
    s=0, size=n*n;
    memset((void*)&map[0][0], 0xff, MAXEL*MAXEL);//all -1
    memset((void*)&lef[0][0], 0x4, MAXEL*MAXEL);//all 4
    for(int i=0; i<n; i++)
        lef[0][i]=3, lef[i][0]=3, lef[i][n-1]=3, lef[n-1][i]=3;
    lef[0][0]=2,lef[0][1]=2,lef[1][0]=2,lef[0][n-1]=2,lef[n-1][n-1]=2, lef[n-1][0]=2;
    map[0][0]=0;//first step
}

void expand(int step1, int x, int y){
    if(step1==size&&x==n-1&&y==0){
        s++;
        return;
    }
    //[1…n*n-1]
    int nx,ny,fx,fy;
    for(int i=0; i<MAXDIR; i++){
        //n*n-1 step
        nx=x+fd[i][0], ny=y+fd[i][1];
        if(nx==n-1&&ny==0&&step1==size-1&&map[nx][ny]==-1){//last step to (n-1, 0)
            expand(step1+1, nx, ny);//dummay implementation
        }
        else if(nx>-1&&nx<n&&ny>-1&&ny<n&&map[nx][ny]==-1){//continue
            if(cut1(i, x, y)||cut2(i, x, y)) continue;
            //set information
            map[nx][ny]=0;
            for(int j=0; j<MAXDIR; j++){
                fx=nx+fd[j][0], fy=ny+fd[j][1];//error for parameters!
                if(fx>-1&&fx<n&&fy>-1&&fy<n)
                    lef[fx][fy]–;
            }
            expand(step1+1, nx, ny);
            //reset information
            map[nx][ny]=-1;
            for(int j=0; j<MAXDIR; j++){
                fx=nx+fd[j][0], fy=ny+fd[j][1];
                if(fx>-1&&fx<n&&fy>-1&&fy<n)
                    lef[fx][fy]++;
            }
        }
    }
}

bool cut1(int dir, int x, int y){
    int nx, ny;
    for(int i=0; i<MAXDIR; i++){//take care of i<N
        if(i!=dir){
            nx=x+fd[i][0], ny=y+fd[i][1];
            if(nx>-1&&nx<n&&ny>-1&&ny<n){
                if(nx==0&&ny==0) continue;
                if(nx==n-1&&ny==0) continue;
                if(map[nx][ny]==-1&&lef[nx][ny]<=1)  return true;
            }
        }
    }
    return false;
}

bool cut2(int dir, int x, int y){//nx, ny is valid
    int nx=x+fd[dir][0], ny=y+fd[dir][1],d1,d2;
    int fx=nx+fd[dir][0], fy=ny+fd[dir][1];
    if(dir==0||dir==2) d1=1,d2=3;
    else d1=0,d2=2;
    int lx,ly,rx,ry,lnx,lny,rnx,rny;
    if(fx>-1&&fx<n&&fy>-1&&fy<n){//0 for right, 1 for left
        if(map[fx][fy]!=-1){
            //case 1: cut into two parts
            lx=nx+fd[d1][0], ly=ny+fd[d1][1], rx=nx+fd[d2][0], ry=ny+fd[d2][1];
            if(lx>-1&&lx<n&&ry>-1&&ry<n&&map[lx][ly]==-1&&map[rx][ry]==-1)
            return true;
        }
        else{
            //case 2: left part, (x,y) and (nx, ny)
            lx=nx+fd[d1][0], ly=ny+fd[d1][1], lnx=fx+fd[d1][0], lny=fy+fd[d1][1];
            if(lx>-1&&lx<n&&ly>-1&&ly<n&&lnx>-1&&lnx<n&&lny>-1&&lny<n&&
                map[lnx][lny]!=-1&&map[lx][ly]==-1)//corner
                return true;
            //case 3: right part, (x,y) and (nx, ny) ?
            rx=nx+fd[d2][0], ry=ny+fd[d2][1], rnx=fx+fd[d2][0], rny=fy+fd[d2][1];//error!
            if(rx>-1&&rx<n&&ry>-1&&ry<n&&rnx>-1&&rnx<n&&rny>-1&&rny<n&&
                map[rnx][rny]!=-1&&map[rx][ry]==-1)
                return true;
        }
    }
    //case 4: last corner
    if(nx==n-2&&ny==1&&map[n-2][0]==-1&&map[n-1][1]==-1) return true;
    return false;
}

#define fbase
int main()
{
    #ifdef fbase
    ifstream in("input.txt");
    if(!in) return EXIT_FAILURE;
    cin.rdbuf(in.rdbuf());
    #endif

    //implementation
    while(cin>>n&&n!=0){
        init();
        expand(1, 0, 0);
        cout<<s<<endl;
    }

    #ifdef fbase
    in.close();
    #endif
    return 0;
}
#undef fbase

  • 基于状态压缩的动态规划

1,状态分解:DFS实际上是一步一格,那么能否一步多格呢?当然可以,分析为以下6种情况。

相对于单步而言,“2连”以及“3连”当然更快!下面的问题是如何将N*N的棋盘分解:

先膜拜下一位神牛的论文再编码吧!想呀想呀想,有点眉目了,但还达不到lrj的那种思路,先看能否用cdq的思路写一个,直觉告诉我,lrj的那个思路还改进的很多!

先贴个自己的分析,唉!才证明完cdq的命题,我只能说这个小女生太强大了,EOI特别奖得主,真的不是盖的!“有志不在年高,无知空活百岁”!本菜是被神牛cdq折服了,惭愧惭愧,白长了人家那么多岁,一看人家的论文,真的是惭愧到无地自容,除了加倍努力,还能做什么,惭愧加加倍努力吧!

经过仔细分析,发现那个算法有两个小漏洞[加一个完备性的证明],估计能达到O(N^2*2^N),加上lrj的优化[剪枝动归逻辑已经有了,不过“判断”的提前量不大,不过本菜认为可以在动归的框架里面加入这个逻辑的],应该会相当快!

Advertisements