台州OJ 3709: Number Maze （数组越界不报RE，报WA坑爹）

http://acm.tzc.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=3709

You are playing one game called "Number Maze". The map of an example is shown in the following figure.

In the map, there are N*N+2 cells. When the game starts, you stay the top-left cell and you target is to reach the bottom-right cell with fewest number of moves. At the first step, you must move to the right of the start cell. After that, you can move to any cell (left, right, up or down, but can not move diagonally) if the target cell can be divided by the sum of the previous two numbers. However, you should never move backwards. For example, at first, you stay at the "2" cell, and you must move to the "6" cell, then have two selections "8" or "4" because (2+6)/8=1 and (2+6)/4=2, you can not move back to the "2" cell at this step although (2+6)/2=4. One possilbe solution is 2->6->8->7->5->3->4->7->11->2->13, and the total number of moves is 10.
Another solution is also legal but has longer moves:
2->6->8->7->5->3->4->7->5->3->4->7->11->2->13

Input

 

Thare are at most 20 cases. The first line of each case has three integers N<=10, S and T, which N indicates the dimension of the map, S and T indicate the number in the start and target cell. Then follows N lines and each line has N positive integers which indicate each number in the N*N cells.
There has one blank line after each case and you can assume that the total number of all cells is no larger than 1000000.

The inputs are ended with End of File. If you have some questions, please visit the help page.

Output

 

Each case outputs the fewest number of moves or "Impossible" if you can not reach the target cell per line.
 

Sample Input

3 2 13
6 4 3
8 7 5
2 11 2

Sample Output

题意：

给出一张这样的地图，由左上角的2开始，目标是走到右下角的13，走的时候，要求：1-->2，当2-->3的时候，要求1和2两个值相加的和能整除3那个点的值，并且不能返回走，就是走去3了后，就不能回到2了。(这个条件是很重要的，不然有bug)

思路：很简单，直接bfs，同时记录一个fa值，表示这个点是从那个点走过来的，就可以了。

然后做的时候无限wa，然后我就把路径输出来了，和样例一模一样，我觉得没可能错的啊。然后就想了一组数据，是死循环的数据，我没判断。然后我的做法是，对于一个10*10的数组，虽然可以重复走一些步数，但是扩展步数也有限的，900步，还要继续走就是死循环了，改了后居然过了。原来一开始我的数组开得太小了，才100，越界后，修改了其它内存，然后没报RE而是wa。找了很久的bug。唉。。但是我居然发现网上的代码，过不了我这组死循环数据（网上代码RE），然后那个代码是AC的。~~~~~！！！！！！

3 1 100
1 1 1
1 1 1
1 1 1

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define inf (1<<28)
typedef long long int LL;

#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <conio.h>
int n,s,t;
const int maxn=12;
int a[maxn][maxn];
struct data
{
    int x,y;
    int count;
    int fa;
};
int next[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
int bfs (int bx,int by,int endx,int endy)
{
    struct data que[100*10+20]={0};//这个数组开大点吧
    int head,tail;
    head=tail=1;
    int flag=0;
    que[0].fa=-1;
    que[0].x=bx;
    que[0].y=by;//开始的做上交那个格子

    que[tail].count=1;//第一步是固定的，从左上角那个走过来
    que[tail].fa=0;
    que[tail].x=2;
    que[tail].y=2;
    tail++;
    
    flag++;//标记走了几步，防止死循环
    while (head<tail)
    {
        for (int i=0;i<4;i++)
        {
            flag++;
            if (flag==900)//没可能走900步那么多的
            {
                return inf;
            }
            int tx=que[head].x+next[i][0];
            int ty=que[head].y+next[i][1];
            //(tx==que[que[head].fa].x && ty==que[que[head].fa].y
            //判断不能返回走，必须判断
            if (tx>=2&&tx<=n+2&&ty>=2&&ty<=n+2&&!(tx==que[que[head].fa].x && ty==que[que[head].fa].y))
            {
                int x=que[que[head].fa].x;
                int y=que[que[head].fa].y;
                int add=a[que[head].x][que[head].y]+a[x][y];
                if (add%a[tx][ty]==0)
                {
                    //printf ("%d  %d %d
",add,tx,ty);
                    //getch();
                    que[tail].x=tx;
                    que[tail].y=ty;
                    que[tail].fa=head;
                    que[tail].count=que[head].count+1;
                    if (tx==endx && ty==endy)
                    {
                        return que[tail].count;
                    }
                    tail++;
                }
            }
        }
        head++;
    }
    return inf;
}
void work ()
{
    for (int i=1;i<=maxn-1;i++)
    {
        for (int j=1;j<=maxn-1;j++)
        {
            a[i][j]=inf;
        }
    }//全部设置为inf
    //我把整个地图右下移动了一格
    a[2][1]=s;
    for (int i=2;i<=n+1;i++)
    {
        for (int j=2;j<=n+1;j++)
        {
            scanf ("%d",&a[i][j]);
        }
    }
    a[n+1][n+2]=t;
    /*
    for (int i =1;i<=n+2;i++)
    {
        for (int j=1;j<=n+2;j++)
        {
            printf ("%10d ",a[i][j]);
        }
        printf ("
");
    }*/
    int ans=bfs (2,1,n+1,n+2);
    if (ans==inf)
    {
        printf ("Impossible
");
    }
    else printf ("%d
",ans);
    return ;

}

int main ()
{
    #ifdef local
    freopen("data.txt","r",stdin);
    #endif
    while (scanf ("%d%d%d",&n,&s,&t)!=EOF)
    {
        work ();
    }
    return 0;
}

虽然是过了，回想一下，还有一个地方值得思考，那就是，为什么不能回头走。刚开始的时候我还以为这里我判断错了，然后又造不出回头走wa的数据，现在用严格的数学证明下，回头走是会wa的。

假设我们走到了Y,然后(X+Y)%targe!=0    ① (就是说在Y那个格子，从X走过来的话，不能到达目标)

但是能走到Z  ==>  (X+Y)%Z==0  ②

假设，假设，我们能回头走，走回Y，有(Z+Y)%Y==0  ③

然后，我们能达到目标了（这样会wa了吧） (Z+Y)%targe==0 

现在我们求解一组X,Y,Z

由②式有，X+Y=K1*Z; ==>(结合下面的) X=(K1*K2-K1-1)Y;

由③式有，Z+Y=K2*Y;  ==>  Z=(K2-1)*Y;

取K1=7  K2=3

解出

X=13Y

Y=Y

Z=2Y

那么我们的targe是3Y即可

所以，不能返回走是必要的，有数据坑你的

本人初出茅庐，如果有哪里错误的地方，还请读者多多指出，本人感激不尽！