首页 > ACM题库 > 九度OJ > 九度-1384-二维数组中的查找[解题代码]
2013
12-13

九度-1384-二维数组中的查找[解题代码]

题目描述:

在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。

输入:

输入可能包含多个测试样例,对于每个测试案例,

输入的第一行为两个整数m和n(1<=m,n<=1000):代表将要输入的矩阵的行数和列数。

输入的第二行包括一个整数t(1<=t<=1000000):代表要查找的数字。

接下来的m行,每行有n个数,代表题目所给出的m行n列的矩阵(矩阵如题目描述所示,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。

输出:

对应每个测试案例,

输出”Yes”代表在二维数组中找到了数字t。

输出”No”代表在二维数组中没有找到数字t。

样例输入:
3 3
5
1 2 3
4 5 6
7 8 9
3 3
1
2 3 4
5 6 7
8 9 10
3 3
12
2 3 4
5 6 7
8 9 10
样例输出:
Yes
No
No

cpp 代码如下:
#include <iostream>
#include <stdio.h>
using namespace std;
const int M=1001;
int m,n,arr[M][M],t;

bool find(int sx, int sy, int ex, int ey){

	if(sx <= ex && sy <= ey){
		//如果只有一个数了
		if(sx == ex && sy == ey) return arr[sx][sy] == t;
		int midx = (sx+ex)/2;
		int midy = (sy+ey)/2;
		//如果找到就直接返回

		if(sx == midx && sy == midy) return (arr[sx][sy]==t || arr[sx+1][sy]==t || arr[sx][sy+1]==t || arr[sx+1][sy+1]==t);
		//cout << sx << " " << sy << "; " << ex << " " << ey  << "  M:" << midx << " " << midy << "   "  << arr[midx][midy] <<  endl;
		if(arr[midx][midy] == t) return true;
		else if(arr[midx][midy] > t){ // 不可能是右下
			return ( find(sx, sy, midx, midy)
					|| find(midx, sy, ex, midy)
					|| find(sx, midy, midx, ey)
					);
		}else{ //不可能是左上
			return ( find(midx, midy, ex, ey)
					|| find(midx, sy, ex, midy)
					|| find(sx, midy, midx,ey )
					);
		}
	}
	return false;
}


int main() {
	while(scanf("%d%d",&m,&n) != EOF){
		scanf("%d", &t);
			for(int i=0; i<m; i++)
				for(int j=0; j<n; j++)
					scanf("%d",&arr[i][j]);

			if(find(0,0, m-1, n-1))
				puts("Yes");
			else
				puts("No");
	}

	return 0;
}
/**************************************************************
	Problem: 1384
	User: coder
	Language: C++
	Result: Accepted
	Time:690 ms
	Memory:5432 kb
****************************************************************/


  1. I like your publish. It is great to see you verbalize from the coronary heart and clarity on this essential subject matter can be easily noticed.