方形矩阵进行Z字形扫描(Zigzag Scan),自己多次测试正常,提交到CCF模拟测试中运行失败

奔波霸儿 发布于 2020/04/07 10:58
阅读 251
收藏 0
问题描述
  在图像编码的算法中,需要将一个给定的方形矩阵进行Z字形扫描(Zigzag Scan)。给定一个n×n的矩阵,Z字形扫描的过程如下图所示:

  对于下面的4×4的矩阵,
  1 5 3 9
  3 7 5 6
  9 4 6 4
  7 3 1 3
  对其进行Z字形扫描后得到长度为16的序列:
  1 5 3 9 7 3 9 5 4 7 3 6 6 4 1 3
  请实现一个Z字形扫描的程序,给定一个n×n的矩阵,输出对这个矩阵进行Z字形扫描的结果。
输入格式
  输入的第一行包含一个整数n,表示矩阵的大小。
  输入的第二行到第n+1行每行包含n个正整数,由空格分隔,表示给定的矩阵。
输出格式
  输出一行,包含n×n个整数,由空格分隔,表示输入的矩阵经过Z字形扫描后的结果。
样例输入
4
1 5 3 9
3 7 5 6
9 4 6 4
7 3 1 3
样例输出
1 5 3 9 7 3 9 5 4 7 3 6 6 4 1 3
评测用例规模与约定
  1≤n≤500,矩阵元素为不超过1000的正整数。

 

我自己用cpp代码实现了(其实就是c语言的写法),自己在DEV5.11上测试1×1、2×2、3×3、4×4、5×5规模方形矩阵结果都是正确的,结果如下。但是一提交到CCF的模拟考试中还是显示“运行错误”,得分为60分。想了很久没有想出来哪个地方出错了,哪个朋友有兴趣指正,一起学习下不?代码在下面。

1
10
10

2
10 2
1  3
10 2 1 3

3
1  3 4
22 3 5
10 2 4
1 3 22 10 3 4 5 2 4

4
1 5 3 9
3 7 5 6
9 4 6 4
7 3 1 3
1 5 3 9 7 3 9 5 4 7 3 6 6 4 1 3

5
1 5 3 9 10
3 7 5 6 11
9 4 6 4 12
7 3 1 3 15
9 2 4 5 20
1 5 3 9 7 3 9 5 4 7 9 3 6 6 10 11 4 1 2 4 3 12 15 5 20

------------------------源码---------------------------------------

#include <iostream>

using namespace std;

const int START=0;//表示没有方向 
const int RIGHT=1;//表示向右 
const int DOWN=2;//表示向下
const int RIGHT_UP=3;//表示向右上 
const int LEFT_DOWN=4;//表示向左下
const int MAX_MATRIX=500;//方形矩阵的最大的大小

void scanNextNode(int(*arr)[MAX_MATRIX], int arrLen, int direct, int i, int j);
//int exercise201412_2()
int main()
{
	int arr[MAX_MATRIX][MAX_MATRIX];//存储所有的输入数据
	int n;//输入的n,表示方形矩阵的真实大小 
	
	scanf("%d", &n);
	for(int i=0; i<n; i++)
	{
		for(int j=0; j<n; j++)
		{
			scanf("%d", &arr[i][j]);
		}
	}
	scanNextNode(arr, n, START, 0, 0);
	return 0;	
}

/*
此方法使用Z字形扫描法扫描方形矩阵中下一个元素
int(*arr)[MAX_MATRIX]二维整型数组 
int arrLen方形矩阵的大小 
int direct元素来的方向 
int i元素横坐标 
int j元素纵坐标 
*/
void scanNextNode(int(*arr)[MAX_MATRIX], int arrLen, int direct, int i, int j)
{
	printf("%d ", arr[i][j]);
	int newI=i,newJ=j;
	int nextDirect=direct;
	//已经扫描到最后一个节点 
	if(i==(arrLen-1) && j==(arrLen-1))
	{
		return;
	}
	
	//当前元素是第一个元素
	if(START==direct)
	{
		nextDirect=RIGHT;	
	}
	else
	{
		//当前元素来的方向是右
		if(direct==RIGHT)
		{
			//向右只会出现在上下边界
			if(i==0 )//上边界元素,当前元素离开的方向是左下 
			{
				nextDirect=LEFT_DOWN;
			}
			else//( i==(arrLen-1) )//下边界元素,当前元素离开的方向是右上
			{
				nextDirect=RIGHT_UP;		
			}
		}
		//当前元素来的方向是下
		else if(direct==DOWN)
		{
			//向下只会出现在左右边界
			if( j==(arrLen-1) )//右边界元素,当前元素离开的方向是左下 
			{
				nextDirect=LEFT_DOWN;
			}
			else//( j==0 )//左边界元素,当前元素离开的方向是右上 
			{
				nextDirect=RIGHT_UP;		
			}
		}
		//当前元素来的方向是右上 
		else if(direct==RIGHT_UP)
		{
			//要改变方向了 
			if((i-1)<0 || (j+1)>(arrLen-1))
			{
				if((i+j)<(arrLen-1))//当前元素在方形矩阵左上半边,不包括左上右下分界线 
				{
					//离开此元素的方向是右
					nextDirect=RIGHT;	
				}
				else//当前元素在方形矩阵右下半边,包括左上右下分界线
				{
					//离开此元素的方向是下
					nextDirect=DOWN;
				}
			}
			//否则不改变方向 
		}
		//当前元素来的方向是左下 LEFT_DOWN
		else
		{
			//要改变方向了 
			if((i+1)>(arrLen-1) || (j-1)<0)
			{
				if((i+j)<(arrLen-1))//当前元素在方形矩阵左上半边,不包括左上右下分界线 
				{
					//离开此元素的方向是下
					nextDirect=DOWN;
				}
				else
				{
					//离开此元素的方向是右
					nextDirect=RIGHT;
				}
			}
			//否则不改变方向 
		}
	}
	
	switch(nextDirect)
	{
		case RIGHT:
			newJ=j+1;
			break;
		case DOWN:
			newI=i+1;
			break;
		case RIGHT_UP:
			newI=i-1;
			newJ=j+1;
			break;
		case LEFT_DOWN:
			newI=i+1;
			newJ=j-1;
	}
	
	scanNextNode(arr, arrLen, nextDirect, newI, newJ);
}

 

加载中
OSCHINA
登录后可查看更多优质内容
返回顶部
顶部