蛇形矩阵 （长沙理工大学第十一届程序设计竞赛）

蛇形矩阵 （长沙理工大学第十一届程序设计竞赛）

 

Home PageDIY ContestsProblemsRanklistStatusStatistics

 

蛇形矩阵

Time Limit : 4000/2000ms (Java/Other)   Memory Limit : 65535/65535K (Java/Other)

Total Submission(s) : 9   Accepted Submission(s) : 1

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

Problem Description

小A最近迷上了玩蛇形矩阵，小B有天路过看到他正玩的入迷，于是就给他出了一道题：按蛇形矩阵的构造顺序构造行和列都为n的矩阵，但是加上一个限制条件，矩阵的奇数行只能填奇数，偶数行只能填偶数。然后给你一个数m，在矩阵中找到两个不同的数a,b，使得a + b = m。
n=3原来的蛇形矩阵构造顺序
1 2 3
8 9 4
7 6 5
n=3改版后的蛇形矩阵构造
1 3 5
4 6 2
11 9 7

n=4原来的蛇形矩阵构造顺序
1 2 3 4
12 13 14 5
11 16 15 6
10 9 8 7
n=4改版后的蛇形矩阵构造
1 3 5 7
12 14 16 2
11 15 13 9
10 8 6 4

Input

多组输入，每组一行，有2个数n(n<=1000),m(m<=1000000000),含义见描述

Output

要求找到两个数的下标和最小（矩阵的下标从左上角（1,1）开始，行为x，列为y，两个数A（x1，y1）B（x2，y2）的下标和为x1 + x2 + y1 + y2）。如果找不到两个数使它们的和等于m输出"no ans"（引号不要输出）

Sample Input

3 5
3 21

Sample Output

5
no ans

---

Statistic | Submit | Back

 

 

主要就是建好矩阵和存贮坐标和

不小心还wa了一次。。唉

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define N 1000000+1500
int stamp[1005][1005];
int coor[N];
int t1,t2,n,cir;
void value(int x,int y)
{if(x%2==0){stamp[x][y]=t1;coor[t1]=x+y+2;t1+=2;}else{stamp[x][y]=t2;coor[t2]=x+y+2;t2+=2;}}
void build()
{for(int i=0;i<=(n-1)/2;i++){for(int j=i;j<n;j++)if(!stamp[i][j])value(i,j);for(int j=i;j<n-i;j++)if(!stamp[j][n-1-i])value(j,n-1-i);for(int j=n-1-i;j>=0;j--)if(!stamp[n-1-i][j])value(n-1-i,j);for(int j=n-1-i;j>i;j--)if(!stamp[j][i])value(j,i);}}
int main()
{int m;while(~scanf("%d %d",&n,&m)){t1=1,t2=2,cir=0;memset(stamp,0,sizeof(stamp));memset(coor,0,sizeof(coor));build();int result=0x3fffffff;t1-=2,t2-=2;int end=max(t1,t2);for(int i=1;i<=end;i++){if(m-i<=0)break;if(m-i<N&&m<N){if(coor[i]&&coor[m-i]&&i!=m-i)result=min(result,coor[i]+coor[m-i]);}}if(result!=0x3fffffff)printf("%dn",result);elseprintf("no ansn");}return 0;
}