扩展欧几里德，ap+bq=c，此题中

a=m-n;
b=-l;
c=y-x;

递归到当b=0是停止此时p一定为1，q值不定，不妨设为0，再递归上去得到p0，然后通解是

p = p0 + b/Gcd(a, b) * t
q = q0 – a/Gcd(a, b) * t

此处有一个小问题 导致了我一直不能AC
设c是gcd的n倍，那么p0*=n，然而后面b/Gcd(a, b) * t要不要乘以n呢，答案是不要，没搞清楚为什么，反正不乘就过了..

#include <cstdio>
#include <cmath>
    /*  p = p0 + b/Gcd(a, b) * t
        q = q0 - a/Gcd(a, b) * t
    45 165 63 22 10000          */

__int64 d;

void exgcd(__int64 *p,__int64 *q,__int64 a,__int64 b) {
    __int64 x,y;
    if(!b) {
        *p=1;
        *q=0;
        d=a;
        return;
    }
    exgcd(&x,&y,b,a%b);
    *p=y;
    *q=(x-a/b*y);
    return;
}

int main() {
    __int64 x,y,m,n,l,a,b,c,p,q,t;
    scanf("%I64d%I64d%I64d%I64d%I64d",&x,&y,&m,&n,&l);
    a=m-n;
    b=-l;
    c=y-x;
    exgcd(&p,&q,a,b);
    if(c%d) {
        printf("Impossible\n");
        return 0;
    }
    n=c/d;
    t=(b/d);
    t=t>0?t:-t;
    p=(n*p%t+t)%t;
    printf("%I64d\n",p);
    return 0;
}

爽死了 两个小时又切掉一题某人的fail!
递归大美!!! 我的思维和机器的思维真是惊人的合拍啊^^

思路:
把矩阵分成两个三角矩阵

  -+--
-  ---
--  --
-+-  -

这样然后先对上三角的第一行和下三角的（左起）第一列枚举，接着对上三角第二行和下三角第二列枚举，关键就是在从“一”进入“二”的时候 对左上角的矩形进行判断，这一个矩形是进入“二”以后再也接触不到的一个区域，如果此区域不是全部open那以后的递归就不用做了，大大提高效率 ：） 自己想出来的噢～～ AC32ms 看了比绝大部分人快 也～～

debug用了大半个小时 其实只有一个错……上三角的最后一行没有进行枚举，无法得到结果，浪费那么长时间遗憾啊
debug的时候想到的技巧：因为递归层数太多显然无法一步一步调试 于是我加了这段判定代码：

if(r[0][0]&&!r[0][1]&&r[0][2]&&r[0][3]
 &&!r[1][0]&&!r[1][1]&&!r[1][2]&&!r[1][3]
 &&!r[2][0]&&!r[2][1]&&!r[2][2]&&!r[2][3]
 &&r[3][0]&&!r[3][1]&&r[3][2])
	i=1;

在i=1;上面设breakpoint就可以一步到达终点来调试了..开始多加了个&&r[3][3]因为下面的bug一直搞不出来
擦 来不及了 赶快贴了代码去学校抄作业

#include <cstdio>


bool a[4][4],r[4][4];

void change(int x,int y) {
    int i;
    for(i=0;i<4;i++) {
        a[x][i]=a[x][i]?false:true;
        a[i][y]=a[i][y]?false:true;
    }
    a[x][y]=a[x][y]?false:true;
    r[x][y]=r[x][y]?false:true;
}

bool calc(bool istop,int row,int from) {
    int i,j;

    /*TESTER
    for(i=0;i<4;i++) {
        for(j=0;j<4;j++)
            printf("%d",r[i][j]);
        printf("\n");
    }

    if(r[0][0]&&!r[0][1]&&r[0][2]&&r[0][3]
    &&!r[1][0]&&!r[1][1]&&!r[1][2]&&!r[1][3]
    &&!r[2][0]&&!r[2][1]&&!r[2][2]&&!r[2][3]
    &&r[3][0]&&!r[3][1]&&r[3][2])
        i=1;*/

    if(!istop&&row==3) {
        for(i=0;i<4;i++)
            if((!a[i][3])||(!a[3][i]))
                return false;
        return true;
    }
    if(istop) {
        if(from>3-row)
            return calc(false,row,0);
        if(calc(true,row,from+1))
            return true;
        change(row,from+row);
        if(calc(true,row,from+1))
            return true;
        change(row,from+row);
        return false;
    }
    else {
        if(from>2-row) {
            for(i=0;i<=row;i++)
                if((!a[i][row])||(!a[row][i]))
                    return false;
        return calc(true,row+1,0);
        }
        if(calc(false,row,from+1))
            return true;
        change(row+from+1,row);
        if(calc(false,row,from+1))
            return true;
        change(row+from+1,row);
        return false;
    }
}

int main() {
    int i,j,n;
    for(i=0;i<4;i++) {
        for(j=0;j<4;j++)
            a[i][j]=getchar()=='-'?true:false;
        getchar();
        r[i][j]=false;
    }
    calc(true,0,0);
    n=0;
    for(i=0;i<4;i++)
        for(j=0;j<4;j++)
            if(r[i][j])
                n++;
    printf("%d\n",n);
    for(i=0;i<4;i++)
        for(j=0;j<4;j++)
            if(r[i][j])
                printf("%d %d\n",i+1,j+1);
    return 0;
}

夜里边切题边等电影缓冲真是太爽了..
正在慢慢的切某人切不下来的题..
1573挺简单的 以后这种模拟的数组我都从1开始就好了..省得墨迹墨迹的整的头大..

主要就是想到一个监视指针的方法..做个tester指针数组 对应map上面所有的单元
这样本来看不懂的指针地址(0x22fb18这样)就能通过查找tester来获得它的位置(tester是一个地址的数组 找到对应的 然后数数)

详见下图 ap是tester,p==0x22fb18，在ap中排第10个，则p==*(ap[9])

#include <cstdio>
#include <cstring>
typedef struct spot {
    char c;
    bool b;
    int n;
} Spot;
Spot *p;

void move() {
    switch(p->c) {
        case 'N':
            p-=12;
            break;
        case 'S':
            p+=12;
            break;
        case 'E':
            p+=1;
            break;
        case 'W':
            p-=1;
    }
}

int main() {
    int i,enter,j,n,rows,cols;
    Spot a[12][12];
    /*Tester
    Spot *(ap[3][6]);
    for(i=0;i<3;i++)
        for(j=0;j<7;j++)
            ap[i][j]=a[i]+j;*/
    while(1) {
        for(i=0;i<144;i++) {
            ((Spot *)a+i)->c=-1;
            (a[0]+i)->b=false;
        }
        n=0;
        scanf("%d%d%d",&rows,&cols,&enter);
        if(!rows&&!cols&&!enter)
            return 0;
        getchar();
        for(i=1;i<=rows;i++) {
            for(j=1;j<=cols;j++)
                a[i][j].c=getchar();
            getchar();
        }
        p=a[1]+enter;
        /* TESTER
        for(i=0;i<rows;i++) {
            for(j=1;j<=cols;j++)
                printf("%c",a[i][j].c);
            printf("\n");
        } */
        while(1) {
            p->b=true;
            p->n=n;
            if(p->c==-1) {
                printf("%d step(s) to exit\n",n);
                break;
            }
            move();
            if(p->b) {
                printf("%d step(s) before a loop of %d step(s)\n",p->n,n+1-p->n);
                break;
            }
            n++;
        }
    }
    return 0;
}