现在的位置: 首页 > 综合 > 正文

poj2056

2013年07月26日 ⁄ 综合 ⁄ 共 849字 ⁄ 字号 评论 2 条

题目:http://poj.org/problem?id=2056
这题做的我真是,,,太艰难了, OLE, TLE, WA, WA, TLE, WA, MLE, MLE, TLE, WA, WA, WA, WA, AC -_-||
题意就是给一个N*M的字符型的矩阵,有W, S, B三种字符,可以做出两种变换,一种是S右边的B可以变成S,还有一种是S可以变成W,现在要找一条路径使得所有的S能够把B和W分开。并且要求S的个数最小。一开始用深搜,代码倒是简单,交上去TLE,然后各种优化之后就TLE和WA了,然后改成宽搜,莫名其妙的MLE了,然后各种改。。最后看discuss才知道这题根本就用不着搜索,直接计算就没了,大水题啊。。
代码:

#include<cstdio>
#include<cstring>
#define MAXN 205
char map[MAXN][MAXN];
int l[MAXN];
int main() {
    freopen("poj2056.txt", "r", stdin);
    int N, M, result;
    while(scanf("%d%d", &N, &M), N, M) {
        result = 0;
        for(int i = 0; i < N; ++ i) {
            scanf("%s", map[i]);
            l[i] = -1;
            for(int j = 0; j < M; ++ j) {
                if(map[i][j] == 'S') {
                    if(l[i] == -1) {
                        l[i] = j;
                    }
                    result ++;
                }
            }
        }
        int flag = 2;//flag标志着三种状态,flag = 1是表示左凸,flag = 0表示这段是平的,flag = 2 表示在顶部的时候右凸
        for(int i = 1; i < N; ++ i) {
            if(l[i] < l[i - 1]) {
                flag = 1;
            } else if(l[i] > l[i - 1] && flag != 0) {
                if(flag == 2) {//顶部右凸,就只需保留一个
                    result ++;
                }
                result -= 2;
                flag = 0;
            }
            if(i == N - 1 && flag == 1) {//最后左凸也是一样只保留一个
                result --;
            }
        }
        printf("%d\n", result);
    }
    return 0;
}
【上篇】
【下篇】

目前有 2 条留言    访客:1 条, 博主:1 条


  1. 管理员
    admin 2013年07月26日 下午2:11  Δ-49楼

    陷入误区了吧

    • sunshine945 2013年07月26日 下午3:32  ∇地下1层

      是啊,我做的都快郁闷死了