回形遍历( 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=;
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=,i=,j=,fx=,Maxn=n*m;
while(js<Maxn) {
if(!jz[i][j])
jz[i][j]=++js;
if(i==x && j==y)
Maxn=js+z;
if(fx==) {
j++;
if(j>m || jz[i][j]!=) fx=,j--;
} else if(fx==) {
i++;
if(i>n || jz[i][j]!=) fx=,i--;
} else if(fx==) {
j--;
if(j< || jz[i][j]!=) fx=,j++;
} else if(fx==) {
i--;
if(i< || jz[i][j]!=) fx=,i++;
}
}
printf("%d %d",i,j);
return ;
}
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=,peny=,step=;
int i=n-,j=m-,flag=;
bool right=true,up=false;
bool first=true;
int cnt=;
while(!(step==n*m-)) {
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 ;
}
}
} 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 ;
}
}
}
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 ;
}
}
} 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 ;
}
}
}
i--;
up=!up;
}
flag^=;
}
printf("%d %d",peny,penx);
// fclose(stdin);fclose(stdout);
return ;
}