稀疏矩阵如何提高遍历效率

描述

如果一个函数f(x)，需要读入稀疏矩阵中的非0元素，并根据x对矩阵进行操作。如果要遍历稀疏矩阵中的非0元素，有以下方法：

矩阵用数组存，遍历整个矩阵，判断是否矩阵元素非0，再传入f(x)中。查找效率很低，矩阵读写效率高。
将非0元素存入map中，用迭代器遍历map，再传入f(x)中。查找效率高，矩阵读写效率低（对map进行读写）。
将非0元素存入queue中，矩阵仍然用数组存，每次queue中pop出一个。查找效率高，矩阵读写效率高。（推荐使用！！！）

实际问题

http://www.luogu.org/problem/show?pid=1736#
分别3种实现方法，1 score 60； 2 score 80; 3 score 100;
所以第三种很好，之后都采用第三种。

1 score 60

#include <iostream>
#include <vector>

using namespace std;

vector<vector<bool> > m, m1, m2;

int N, M;

int max(int a, int b){ return a > b ? a : b; }

int main()
{
    cin >> N >> M;
    m.resize(N, vector<bool>(M));
    m1.resize(N, vector<bool>(M));
    m2.resize(N, vector<bool>(M));

    bool all = false;
    for (int i = 0; i < N; i++)
    for (int j = 0; j < M; j++)
    {
        bool is;
        scanf("%d", &is);
        m[i][j] = m1[i][j] = m2[i][j] = is;
        all |= is;
    }

    if (!all)
    {
        cout << 0;
        return 0;
    }

    bool is = true;
    int k = 1, ret = 0;
    while (is)
    {
        is = false;
        for (int i = 0; i < N - k; i++)
        for (int j = 0; j < M - k; j++)
        {
            if (m1[i][j] && m1[i + 1][j + 1] && !m[i + k][j] && !m[i][j + k])
                is = true;
            else
                m1[i][j] = false;
        }
        k++;
    }
    ret = max(ret, k - 1);

    is = true;
    k = 1;
    while (is)
    {
        is = false;
        for (int i = 0; i < N - k; i++)
        for (int j = k; j < M; j++)
        {
            if (m2[i][j] && m2[i + 1][j - 1] && !m[i + k][j] && !m[i][j - k])
                is = true;
            else
                m2[i][j] = false;
        }
        k++;
    }
    ret = max(ret, k - 1);

    cout << ret;

    return 0;
}

2 score 80

#include <iostream>
#include <vector>
#include <set>
using namespace std;

typedef pair<int, int> pa;
typedef set<pa >::iterator spi;

vector<vector<bool> > m;// , m1, m2;
set<pa > m1, m2;

int N, M;

int max(int a, int b){ return a > b ? a : b; }
bool have(set<pa > &mi, int i, int j){return mi.find(pa(i, j)) != mi.end();}


int main()
{
    cin >> N >> M;
    m.resize(N, vector<bool>(M));
    //m1.resize(N, vector<bool>(M));
    //m2.resize(N, vector<bool>(M));

    bool all = false;
    for (int i = 0; i < N; i++)
    for (int j = 0; j < M; j++)
    {
        bool is;
        scanf("%d", &is);
        m[i][j] = is;
        if (is)
        {
            m1.insert(pa(i, j));
            m2.insert(pa(i, j));
        }
        all |= is;
    }

    if (!all)
    {
        cout << 0;
        return 0;
    }

    bool is = true;
    int k = 1, ret = 0;
    while (is)
    {
        is = false;
        for (spi iter = m1.begin(); iter != m1.end();)
        {
            int i = iter->first, j = iter->second;

            if (have(m1, i, j) && have(m1, i + 1, j + 1) && !m[i + k][j] && !m[i][j + k])
            {
                is = true;
                iter++;
            }
            else
                m1.erase(iter++);
        }
        k++;
    }
    ret = max(ret, k - 1);

    is = true;
    k = 1;
    while (is)
    {
        is = false;
        for (spi iter = m2.begin(); iter != m2.end();)
        {
            int i = iter->first, j = iter->second;

            if (have(m2, i, j) && have(m2, i + 1, j - 1) && !m[i + k][j] && !m[i][j - k])
            {
                is = true;
                iter++;
            }
            else
                m2.erase(iter++);
        }
        k++;
    }
    ret = max(ret, k - 1);

    cout << ret;

    return 0;
}

3 score 100

#include <iostream>
#include <vector>
#include <set>
#include <queue>
using namespace std;

typedef pair<int, int> pa;
typedef set<pa >::iterator spi;

vector<vector<bool> > m , m1, m2;
//set<pa > m1, m2;

int N, M;

int max(int a, int b){ return a > b ? a : b; }
bool have(set<pa > &mi, int i, int j){return mi.find(pa(i, j)) != mi.end();}


int main()
{
    cin >> N >> M;
    m.resize(N, vector<bool>(M));
    m1.resize(N, vector<bool>(M));
    m2.resize(N, vector<bool>(M));

    queue<pa> q1, q2;
    bool all = false;
    for (int i = 0; i < N; i++)
    for (int j = 0; j < M; j++)
    {
        bool is;
        //cin >> is;
        scanf("%d", &is);
        m[i][j] = m1[i][j] = m2[i][j] = is;
        if (is)
        {
            q1.push(pa(i, j));
            q2.push(pa(i, j));
        }
        all |= is;
    }

    if (!all)
    {
        cout << 0;
        return 0;
    }


    queue<pa> &q = q1;
    bool is = true;
    int k = 1, ret = 0;
    while (is)
    {
        is = false;
        queue<pa> tq;
        while (!q.empty())
        {
            int i = q.front().first, j = q.front().second;
            q.pop();

            if (i + k >= N || j + k >= M)
                continue;

            if (m1[i][j] && m1[i + 1][j + 1] && !m[i + k][j] && !m[i][j + k])
            {
                is = true;
                tq.push(pa(i, j));
            }
            else
                m1[i][j] = false;
        }
        q = tq;
        k++;
    }
    ret = max(ret, k - 1);

    q = q2;
    is = true;
    k = 1;
    while (is)
    {
        is = false;
        queue<pa> tq;
        while (!q.empty())
        {
            int i = q.front().first, j = q.front().second;
            q.pop();

            if (i + k >= N || j - k < 0)
                continue;

            if (m2[i][j] && m2[i + 1][j - 1] && !m[i + k][j] && !m[i][j - k])
            {
                is = true;
                tq.push(pa(i, j));
            }
            else
                m2[i][j] = false;
        }
        q = tq;
        k++;
    }
    ret = max(ret, k - 1);

    cout << ret;

    return 0;
}