回形遍历( calc .cpp/c/pas)
时间限制：1s
内存 限制： 256MB
【问题 描 述】
给出一个 n*m 的棋盘，按如下方式遍历，请问(x,y)往后 z 步走到的是哪个格子。
【输入】
输入文件名为 calc.in。
一行，包含五个整数：n,m,x,y,z
【输出】
输出文件名为 calc.out。
输出一行，包含两个整数，表示所在格子的横纵坐标
【输入输出样例】
| calc .in | calc .out |
| 4 5 3 0 5 | 2 4 |
【 样例解释 】
【数据说明】
对于 70%的数据，1<=n,m,z<=1000,0<=x<n,0<=y<m
对于 100%的数据，1<=n,m,z<=100000,0<=x<n,0<=y<m
思路:
1)70%的思路:
（使用数组存储的）模拟/搜索
①模拟的话，就弄一个fx记录正在往什么方向走，然后用jz数组记录下来走过的路程，然后特判一下如果走到了(x,y)位置，只需要在继续模拟z步，然后最后输出走到了哪里即可
②搜索的思路其实跟模拟是一样的。。。
2)100%的思路:
因为空间开100000*100000会炸掉，所以上面的模拟/搜索思路已经不能够适用了，所以我们应该想出一种不开数组存数的办法
思路如下:(以下所说的i==横坐标，y==纵坐标)
首先你需要拥有一个n*m的矩阵，然后找寻一下规律，如下图：
首先考虑，如果我们一个一个的来跳的话，跳到最后一定会超时，所以就一排（列）的跳，如图
假设已经跳到了(x,y)所在的行：（之前如何跳就是用当前的i或者是j是否比x或者是y在同一排或者是列，如果不在，就继续成排成列的跳）
然后跟给出的(x,y)中的j进行比较（因为这一排的i都是跟x相同的，只有j不同）。
如果j>y了，那么就说明多走了几步，题目中又需要求从(x,y)往后走z步到达的点的坐标，所以用当前的点的j减去y就是当前点多走的步数（记住我们是一走走一排）。
如果减出来的数比z大（j-y>z）就说明多走了，所以直接在当前的基础（i，j）上往回走j-y-z步即可，即在(x,y)基础上往右直接走z步如图：
如果减出来的数比z小（j-y<z），那么就说明还需要继续走。但是需要在当前的基础（i，j）上走多少步呢？
其实就是用z-(j-y)得出还需要往下走z-j+y步，所以就转入往下的操作，如图：
（往下左上的操作自己手动模拟就好啦~这里就不给出了。。）
坑点:
第一种的时候数组千万别开大了啊啊啊啊！原来空间辣么小（256MB），炸掉了qwq
我safufu的开了100000*100000的数组2333
ps：计算空间是用100000*100000*4/(1024*2)约是38200MB>256MB
上代码:
1)70分无脑模拟（嘻嘻，至于搜索嘛~自己意会意会咯！）
#include<cstdio> #include<iostream> using namespace std; const int Maxx=1011; int jz[Maxx][Maxx]; int n,m,x,y,z; int main() { freopen("calc.in","r",stdin); freopen("calc.out","w",stdout); scanf("%d%d%d%d%d",&n,&m,&x,&y,&z); x++,y++; int js=0,i=1,j=1,fx=1,Maxn=n*m; while(js<Maxn) { if(!jz[i][j]) jz[i][j]=++js; if(i==x && j==y) Maxn=js+z; if(fx==1) { j++; if(j>m || jz[i][j]!=0) fx=2,j--; } else if(fx==2) { i++; if(i>n || jz[i][j]!=0) fx=3,i--; } else if(fx==3) { j--; if(j<1 || jz[i][j]!=0) fx=0,j++; } else if(fx==0) { i--; if(i<1 || jz[i][j]!=0) fx=1,i++; } } printf("%d %d",i,j); return 0; }
2)正解模拟w
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int main() { freopen("calc.in","r",stdin); freopen("calc.out","w",stdout); int m,n,x,y,z; scanf("%d%d%d%d%d",&m,&n,&y,&x,&z); int penx=0,peny=0,step=0; int i=n-1,j=m-1,flag=1; bool right=true,up=false; bool first=true; int cnt=0; while(!(step==n*m-1)) { if(flag) { step+=j; if(right) { peny+=j; if(penx==x && peny>=y) { cnt+=peny-y; y=peny; if(cnt>=z) { printf("%d %d",y-cnt+z,x); // fclose(stdin);fclose(stdout); return 0; } } } else { peny-=j; if(penx==x && peny<=y) { cnt+=y-peny; y=peny; if(cnt>=z) { printf("%d %d",y+cnt-z,x); // fclose(stdin);fclose(stdout); return 0; } } } if(!first) j--; else first=false; right=!right; } else { step+=i; if(up) { penx-=i; if(peny==y && penx<=x) { cnt+=x-penx; x=penx; if(cnt>=z) { printf("%d %d",y,x+cnt-z); // fclose(stdin);fclose(stdout); return 0; } } } else { penx+=i; if(peny==y && penx>=x) { cnt+=penx-x; x=penx; if(cnt>=z) { printf("%d %d",y,x-cnt+z); // fclose(stdin);fclose(stdout); return 0; } } } i--; up=!up; } flag^=1; } printf("%d %d",peny,penx); // fclose(stdin);fclose(stdout); return 0; }