蓝桥杯-156-螺旋矩阵-模拟

题目描述

对于一个 n 行 m 列的表格，我们可以使用螺旋的方式给表格依次填上正整数，我们称填好的表格为一个螺旋矩阵。

例如，一个 4 行 5 列的螺旋矩阵如下：
1 2 3 4 5
14 15 16 17 6
13 20 19 18 7
12 11 10 9 8

输入描述

输入的第一行包含两个整数 n,m，分别表示螺旋矩阵的行数和列数。
第二行包含两个整数 r,c，表示要求的行号和列号。
其中，2≤n,m≤1000，1≤r≤n，1≤c≤m。

输出描述

输出一个整数，表示螺旋矩阵中第 r 行第 c 列的元素的值。

输入输出样例

输入

4 5
2 2

输出

15

代码及注释

//本题通过模拟去解，耗时较长，但思路比较明了
#include <bits/stdc++.h>
#define N 1001
using namespace std;

int dx[4]={0,1,0,-1};  //两个控制方向的数组，当下标为0,1,2,3时分别对应 右 下 左 上
int dy[4]={1,0,-1,0};  
int Map[N][N];  //存储模拟出来的数字
int done[N][N]={0}; 


int main(){
	int n,m,r,c;
	cin>>n>>m>>r>>c;
	
	for(int i=1;i<=n;i++){  
		for(int j=1;j<=m;j++){
			done[i][j]=1;  //将未被模拟区域填1，其余区域默认 0
		}
	}
	int x=1,y=1,j=0;
	Map[1][1]=1; //手动将（1,1）处填上1
	done[1][1]=0; //记录已完成（0）
	for(int i=2;i<=n*m;i++){
		int nextx = x+dx[j];
		int nexty = y+dy[j];
		if(done[nextx][nexty]==0){  //判断下一步是否是边界
			j++;  //碰到边界，换一个方向
			if(j==4)  //右下左上都重复一遍之后，要从"右"继续，令j=0
				j=0;
		}
		x=x+dx[j];
		y=y+dy[j];
		Map[x][y]=i;
		done[x][y]=0;  //已被模拟过的位置写0，当作新的边界
	}
	cout<<Map[r][c];
}