Fork me on GitHub

Wannafly挑战赛17 A

发表于 | 分类于

题目描述

在平面上有n*n大小的正方形，定义正方形左下角坐标是(1,1)，右下角坐标是(n,1)
现在A君在左下角，他的初始方向是向右，他要在正方形内走m步

当A君碰到边界或者已经走过的格子时，他便会逆时针转90°继续走，直到走完m步。
现在给你两个整数n和m，请算出走完m步后A君的坐标。

输入描述:

输入一行两个整数n和m。

输出描述:

输出一行两个数表示A君的坐标。

输入

3 3

输出

3 2

思路：

直接按题意模拟即可。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define LL long long
#define ULL unsigned long long
#define bug(x) cout<<"bug-----"<<x<<endl
#define R(i,n) for(int i = 0; i < n; i++)
using namespace std;
const int mod= 1e9+7;
const int maxn = 1e3 +10;
int dir[][2]={{0,1},{-1,0},{0,-1},{1,0}};
int vis[maxn][maxn];
int stx,sty;
int n,m;
void dfs(int step,int where)
{
    if(step<=0)
        return ;
    int x1=stx+dir[where][0];
    int y1=sty+dir[where][1];
    //cout<<x1<<" "<<y1<<endl;
    if(x1>0&&x1<=n&&y1>0&&y1<=n&&vis[x1][y1]==0)
    {
        stx=x1;
        sty=y1;
        vis[x1][y1]=1;
        //cout<<x1<<" "<<y1<<endl;
        dfs(step-1,where);
    }
    else
    {
        //bug(1);
        //cout<<x1<<" "<<y1<<endl;
        dfs(step,(where+1)%4);
    }
}
int main(){
    //freopen("C:\\Users\\admin\\Desktop\\1.in","r",stdin);
    //freopen("C:\\Users\\admin\\Desktop\\1.out","w",stdout);
    std::ios::sync_with_stdio(false);
    cin>>n>>m;
    stx=n;
    sty=1;
    vis[stx][sty]=1;
    dfs(m,0);
    cout<<sty<<" "<<n-stx+1<<endl;

    return 0;
}