ACM学习历程—SNNUOJ1215 矩阵2(二分 && dfs)

http://219.244.176.199/JudgeOnline/problem.php?id=1215

这是这次微软和百度实习面试的一道题，题目大意就是：有一个n*m的矩阵，已知它每一行都是不严格递增的，而且每一列都是不严格递增。给你一个数k，请你判断k是否存在于矩阵中。

微软面试的时候没有想到很好的做法，后来想了好久，发现就是一个在矩形上的二分。对于一个矩形，我选取中间一列mid列二分，那么能得到一个index，如果a[index][mid]不为k，那么index以上的都小于k，index以下的都大于k。根据行和列都递增，那么mid列之前且index之上都小于k，在mid列之后且index之下的都大于k。于是这个矩形的空间就可以缩成mid列之后且index之上和在mid列之前且index之下的两块区域，而且两块区域的和为原矩形的一般。如果递归下去就可以解决了。时间复杂度log(nm)*logn

代码：

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cstring>

#include <algorithm>

#include <set>

#include <map>

#include <queue>

#include <vector>

#include <string>

#define LL long long

using namespace std;

const int maxN = ;

int a[maxN][maxN];

int n, m, q;

void input()

{

    for (int i = ; i < n; ++i)

        for (int j = ; j < m; ++j)

            scanf("%d", &a[i][j]);

}

int binSearch(int col, int from, int to, int k)

{

    int lt = from, rt = to, mid;

    while (lt+ < rt)

    {

        mid = (lt+rt)>>;

        if (a[mid][col] <= k) lt = mid;

        else rt = mid;

    }

    if (a[rt][col] <= k) return rt;

    else return lt;

}

bool dfs(int fromx, int fromy, int tox, int toy, int k)

{

    if (fromx >= n || fromy >= m || tox <  || toy < ) return false;

    if (fromx > tox || fromy > toy) return false;

    int mid, index;

    bool ans = false;

    mid = (fromy+toy)>>;

    index = binSearch(mid, fromx, tox, k);

    if (a[index][mid] == k) return true;

    else if (a[index][mid] > k) index--;

    ans = ans || dfs(fromx, mid+, index, toy, k);

    ans = ans || dfs(index+, fromy, tox, mid-, k);

    return ans;

}

void work()

{

    int k;

    scanf("%d", &q);

    for (int i = ; i < q; ++i)

    {

        scanf("%d", &k);

        if (dfs(, , n-, m-, k)) printf("Yes\n");

        else printf("No\n");

    }

}

int main()

{

    //freopen("test6.in", "r", stdin);

    //freopen("test6.out", "w", stdout);

    while (scanf("%d%d", &n, &m) != EOF)

    {

        input();

        work();

    }

    return ;

}