NOIP2014-J-3-螺旋矩阵 WA

常规
1

** 8. NOIP2014-J-3-螺旋矩阵

题目ID：8160100分

时间限制: 1000ms

空间限制: 512000kB

题目描述

一个 n行n列的螺旋矩阵可由如下方法生成：从矩阵的左上角（第1行第1列）出发，初始时向右移动；如果前方是未曾经过的格子，则继续前进，否则右转；重复上述操作直至经过矩阵中所有格子。根据经过顺序，在格子中依次填入1,2,3,…,n，便构成了一个螺旋矩阵。给出矩阵大小n以及i和j，请你求出该矩阵中第i行第j列的数是多少。

输入格式

三个整数n,i,j

输出格式

一个整数，表示答案。

样例

Input 1

4 2 3

Output 1

14

样例解释

将填数的过程依次写出来，就会发现第2行第3列的数是14。

数据范围

1<=i,j<=n<=2000**
我的代码

#include<bits/stdc++.h>
#define LL long long 
using namespace std;
LL a[2005][2005];
LL n,x,y;
bool vis[2005][2005];
LL dx[]={0,1,0,-1};
LL dy[]={1,0,-1,0};
void dfs(LL sx,LL sy,LL cnt,LL d){
    vis[sx][sy]=1;
    a[sx][sy]=cnt;
    LL nx=sx+dx[d];
    LL ny=sy+dy[d];
    if(nx<1||nx>n||ny<1||ny>n||vis[nx][ny]){
        d=(d+1)%4;
    }
    if(cnt==n*n){
        return ;
    }
    // cout<<"cnt:"<<cnt<<"\n:";
    // for(LL i=1;i<=n;i++){
    //     for(LL j=1;j<=n;j++){
    //         printf("% 4lld ",a[i][j]);
    //     }
    //     cout<<"\n";
    // }
    // cout<<"----------------------------------------\n";
    dfs(nx,ny,cnt+1,d);
}
int main(){
    cin>>n>>x>>y;
    dfs(1,1,1,0);
    // for(LL i=1;i<=n;i++){
    //     for(LL j=1;j<=n;j++){
    //         printf("% 4lld ",a[i][j]);
    //     }
    //     cout<<"\n";
    // }
    cout<<a[x][y]<<"\n";
	return 0;
}

快救救我！！！
答出来的奖励一解决方案

2 个赞
2

看了一下啊，错挺多的。

  1. 复杂度不对。其实这个不大要紧，实际上原题里 n \le 30000，但是 xyd 里的很小，你的暴力如果改正确也可以 A。
  2. 你在修改完方向以后没有更新，比如你一旦超出范围了，就算改了方向但是也在界外！

代码改了一下：

void dfs(LL sx,LL sy,LL cnt,LL d){
    vis[sx][sy]=1;
    a[sx][sy]=cnt;
    LL nx=sx+dx[d];
    LL ny=sy+dy[d];
    if(nx<1||nx>n||ny<1||ny>n||vis[nx][ny]){
        d=(d+1)%4;
    }
	nx=sx+dx[d];
    ny=sy+dy[d];
    if(cnt==n*n){
        return ;
    }
    // cout<<"cnt:"<<cnt<<"\n:";
	// cout << nx << ' ' << ny << '\n';
    // for(LL i=1;i<=n;i++){
    //     for(LL j=1;j<=n;j++){
    //         printf("% 4lld ",a[i][j]);
    //     }
    //     cout<<"\n";
    // }
    // cout<<"----------------------------------------\n";
    dfs(nx,ny,cnt+1,d);
}
2 个赞
3

谢谢

1 个赞