C++博客-Search-For-My-Way

各种最短路径，人太懒~

彭托 — Mon, 17 Sep 2012 09:54:00 GMT

http://221.192.240.22/index.php/%E6%9C%80%E7%9F%AD%E8%B7%AF%E5%BE%84

彭托 2012-09-17 17:54 发表评论

马踏棋盘所用的两个向量数组

彭托 — Thu, 13 Sep 2012 03:26:00 GMT

int direct[8][2]={2,1,2,-1,-2,1,-2,-1,1,2,-1,2,1,-2,-1,-2}; //落脚点向量
int judge[4][2]={1,0,-1,0,0,1,0,-1}; //卡位向量

这里说明一下，在使用的时候可以不用太麻烦，我特意将两个向量对应了起来，如

for(i=0;i<4;i++)
        {
            if(chess[pos.x+judge[i][0]][pos.y+judge[i][1]]!=1)           //是否卡位
            {
                int x=pos.x+direct[i*2][0];
                int y=pos.y+direct[i*2][1];
                if(x<=p&&x>=1&&y<=q&&y>=1&&visited[x][y]!=1&&chess[x][y]!=1)  //该点能否落脚
                {
                    visited[x][y]=1;
                    temp.x=x;
                    temp.y=y;
                    temp.step=pos.step+1;
                    que.push(temp);
                }
                x=pos.x+direct[i*2+1][0];
                y=pos.y+direct[i*2+1][1];
                if(x<=p&&x>=1&&y<=q&&y>=1&&visited[x][y]!=1&&chess[x][y]!=1)   //该点能否落脚
                {
                    visited[x][y]=1;
                    temp.x=x;
                    temp.y=y;
                    temp.step=pos.step+1;
                    que.push(temp);
                }
            }
        }

彭托 2012-09-13 11:26 发表评论

很好用的矩阵快速幂，给自己留模版<转，原地址忘了>

彭托 — Wed, 12 Sep 2012 11:36:00 GMT

#include
#define Max 2
#define kmod 7
typedef struct Matrix{
    int M[Max][Max];
}Matrix;
Matrix P;           //等比矩阵,在main中修正;
Matrix I={1,0,
          0,1}; //单位矩阵,需根据Max扩大;
Matrix Matrixmul(Matrix a,Matrix b){  //矩阵乘法;
    Matrix ret;
    int i,j,k;
    for(i=0;i        for(j=0;j        {
            ret.M[i][j]=0;
            for(k=0;k                ret.M[i][j]+=(a.M[i][k]*b.M[k][j])%kmod;
            ret.M[i][j]%=kmod;
        }
    return ret;
}
Matrix quickpow(__int64 n){     // 快速幂;
    Matrix m=P,b=I;
    while(n>0){
        if(n&1)
            b=Matrixmul(b,m);
        n>>=1;
        m=Matrixmul(m,m);
    }
    return b;
}

彭托 2012-09-12 19:36 发表评论