擦 犯了个很愚蠢的错误

错了4组数据。问题发生在哪里？看来我的想法还不完备。有意思。先把代码发上来。

#include<stdio.h>

#define LEN        600

int map[LEN][LEN], n, m;
int lr[LEN * LEN], lc[LEN * LEN];
int tcount, bcount, vlen;
char top[LEN], bottom[LEN], v[LEN][LEN];

int flood(int col, char * mk)
{
    int len, br, r, c, h, t, i, count = 0;
    char f[LEN][LEN] = {0};

    br = n - 1;
    f[lr[0] = 0][lc[0] = col] = 1;
    if(lr[0] == br) count++;
    for(len = 1, i = 0; count < m && i < len; i++)
    {
        r = lr[i];
        c = lc[i];
        h = map[r][c];
        if((t = r - 1) >= 0 && map[t][c] < h && f[t][c] == 0)
        {
            f[t][c] = 1;
            lr[len] = t;
            lc[len++] = c;
        }
        if((t = c + 1) < m && map[r][t] < h && f[r][t] == 0)
        {
            f[r][t] = 1;
            lr[len] = r;
            lc[len++] = t;
            if(r == br) count++;
        }
        if((t = r + 1) < n && map[t][c] < h && f[t][c] == 0)
        {
            f[t][c] = 1;
            lr[len] = t;
            lc[len++] = c;
            if(t == br) count++;
        }
        if((t = c - 1) >= 0 && map[r][t] < h && f[r][t] == 0)
        {
            f[r][t] = 1;
            lr[len] = r;
            lc[len++] = t;
            if(r == br) count++;
        }
    }
    for(i = 0; i < m; i++)
    {
        if(f[0][i] && !top[i])
        {
            top[i] = 1;
            tcount++;
        }
        mk[i] = f[br][i];
        if(mk[i] && !bottom[i])
        {
            bottom[i] = 1;
            bcount++;
        }
    }
    return count;
}

void analyze(int * out1, int * out2)
{
    int count, i, j, k;
    int b[LEN] = {0}, bv[LEN] = {0};
   
    for(i = 0; i < m; i++) top[i] = bottom[i] = 0;
    for(tcount = bcount = vlen = i = 0; tcount < m;)
    {
        while(top[i]) i++;
        while(i < m - 1 && map[0][i] < map[0][i + 1]) i++;
        count = flood(i, v[vlen]);
        if(count) vlen++;
        if(count == m)
        {
            *out1 = 1;
            *out2 = 1;
            return;
        }
    }
    if(bcount < m)
    {
        *out1 = 0;
        *out2 = m - bcount;
        return;
    }
    for(i = 0; i < vlen; i++)
    {
        for(bv[i] = 1, j = 0; j < m; j++) b[j] += v[i][j];
        for(k = 0; k <= i; k++)
        {
            if(!bv[k]) continue;
            for(j = 0; j < m && (!v[k][j] || b[j] > 1); j++);
            if(j < m) continue;
            for(j = 0; j < m; j++) b[j] -= v[i][j];
            bv[k] = 0;
        }
    }
    for(*out1 = 1, *out2 = 0, i = 0; i < vlen; i++) *out2 += bv[i];
}

int main()
{
    int i, j;
    scanf("%d%d", &n, &m);
    for(i = 0; i < n; i++)
    for(j = 0; j < m; scanf("%d", &map[i][j++]));
    analyze(&i, &j);
    printf("%d\n%d\n", i, j);
    return 0;
}

晕死，AC了，原来是一处笔误导致的问题。看看大家的眼力如何能不能找得到。大家先看看代码，如果哪位看懂了欢迎替我解释。

#include<stdio.h>

#define LEN        600

int map[LEN][LEN], n, m;
int lr[LEN * LEN], lc[LEN * LEN];
int tcount, bcount, vlen;
char top[LEN], bottom[LEN], v[LEN][LEN];

int flood(int col, char * mk)
{
    int len, br, r, c, h, t, i, count = 0;
    char f[LEN][LEN] = {0};

    br = n - 1;
    f[lr[0] = 0][lc[0] = col] = 1;
    if(lr[0] == br) count++;
    for(len = 1, i = 0; count < m && i < len; i++)
    {
        r = lr[i];
        c = lc[i];
        h = map[r][c];
        if((t = r - 1) >= 0 && map[t][c] < h && f[t][c] == 0)
        {
            f[t][c] = 1;
            lr[len] = t;
            lc[len++] = c;
        }
        if((t = c + 1) < m && map[r][t] < h && f[r][t] == 0)
        {
            f[r][t] = 1;
            lr[len] = r;
            lc[len++] = t;
            if(r == br) count++;
        }
        if((t = r + 1) < n && map[t][c] < h && f[t][c] == 0)
        {
            f[t][c] = 1;
            lr[len] = t;
            lc[len++] = c;
            if(t == br) count++;
        }
        if((t = c - 1) >= 0 && map[r][t] < h && f[r][t] == 0)
        {
            f[r][t] = 1;
            lr[len] = r;
            lc[len++] = t;
            if(r == br) count++;
        }
    }
    for(i = 0; i < m; i++)
    {
        if(f[0][i] && !top[i])
        {
            top[i] = 1;
            tcount++;
        }
        mk[i] = f[br][i];
        if(mk[i] && !bottom[i])
        {
            bottom[i] = 1;
            bcount++;
        }
    }
    return count;
}

void analyze(int * out1, int * out2)
{
    int count, i, j, k;
    int b[LEN] = {0}, bv[LEN] = {0};
   
    for(i = 0; i < m; i++) top[i] = bottom[i] = 0;
    for(tcount = bcount = vlen = i = 0; tcount < m;)
    {
        while(top[i]) i++;
        while(i < m - 1 && map[0][i] < map[0][i + 1]) i++;
        count = flood(i, v[vlen]);
        if(count) vlen++;
        if(count == m)
        {
            *out1 = 1;
            *out2 = 1;
            return;
        }
    }
    if(bcount < m)
    {
        *out1 = 0;
        *out2 = m - bcount;
        return;
    }
    for(i = 0; i < vlen; i++)
    {
        for(bv[i] = 1, j = 0; j < m; j++) b[j] += v[i][j];
        for(k = 0; k <= i; k++)
        {
            if(!bv[k]) continue;
            for(j = 0; j < m && (!v[k][j] || b[j] > 1); j++);
            if(j < m) continue;
            for(j = 0; j < m; j++) b[j] -= v[k][j];
            bv[k] = 0;
        }
    }
    for(*out1 = 1, *out2 = 0, i = 0; i < vlen; i++) *out2 += bv[i];
}

int main()
{
    int i, j;
    scanf("%d%d", &n, &m);
    for(i = 0; i < n; i++)
    for(j = 0; j < m; scanf("%d", &map[i][j++]));
    analyze(&i, &j);
    printf("%d\n%d\n", i, j);
    return 0;
}

收到的鲜花

• 有容就大 于 2012-08-19 23:20 送鲜花  10朵   附言：牛 就一个字啊 哈哈

杨大哥 我这个是错在哪？ 你怎么知道错了四组数据的？

我的代码已经AC，在55楼。

[ 本帖最后由 demonleer 于 2012-8-20 10:46 编辑 ]

它的结果中有提示啊。你最后一次提交的结果7组正确，3组错误。再前一次提交是超时了，应该发生在第9组数据，之前有5组正确，3组错误。

我去洗个澡，回来看你代码。

原来那几个数字是这个意思， 7AC,3WA，我擦 错哪儿了 NND

呵呵 我找到了。
 for(j = 0; j < m; j++) b[j] -= v[i][j];这个要换成
 for(j = 0; j < m; j++) b[j] -= v[k][j];

正确。大家由此也可以看出编程是多么需要细心严谨的活了吧。仅仅敲错一个字符，编译过程无法发现，还能成功地解决部分问题。一度让你怀疑是理论出了问题。

有点晚了，我明天再看吧。大家也该休息了，睡前不宜做使大脑兴奋的事。

呵呵 光顾看了 都忘了评分啦