题目: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; } |
管理员 admin: 2013年07月26日 下午2:11 Δ-49楼
陷入误区了吧
是啊,我做的都快郁闷死了