题目A:
题目B【https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=614】
题意：
You are given a string consisting of parentheses () and []. A string of this type is said to be correct:
(a) if it is the empty string
(b) if A and B are correct, AB is correct,
(c) if A is correct, (A) and [A] is correct.
Write a program that takes a sequence of strings of this type and check their correctness. Your program can assume that the maximum string length is 128.
题解：虽然长度最长只有128，但是是多组输入，用区间DP会TLE。简单stack的应用。
#include<stack> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int INF = 1e6; const int MAXN = 150; char S[MAXN]; int T, N; int main () { scanf("%d", &T); getchar(); while(T--) { gets(S + 1); N = strlen(S + 1); if(S[1] == ‘ ‘)//第一种情况 { printf("Yes\n"); continue; } stack<char>st; for(int i = 1; i <= N; i++) { if(!st.empty() && ((st.top() == ‘(‘ && S[i] == ‘)‘) || (st.top() == ‘[‘ && S[i] == ‘]‘))) st.pop();//匹配 else st.push(S[i]); } if(st.empty()) printf("Yes\n"); else printf("No\n"); } return 0; }
题目E【http://poj.org/problem?id=2386】
题意：给出一个图，mp[i][j]==‘.‘表示该地为干，mp[i][j]=‘W‘表示该地是水坑，两个水坑联通的条件是八个方向任意一个方向联通则联通。求不联通水坑的个数。
题解：DFS,DFS的次数表示非联通水坑的数量。
#include<stack> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long LL; const int MAXN = 150; char mp[MAXN][MAXN]; int N, M; void DFS(int x, int y) { mp[x][y] = ‘.‘; for(int i = -1; i <= 1; i++) for(int j = -1; j <= 1; j++) if(mp[x+i][y+j] == ‘W‘) DFS(x+i, y+j); } int main () { int ans = 0; scanf("%d%d", &N, &M); for(int i = 1; i <= N; i++) scanf("%s", mp[i] + 1); for(int i = 1; i <= N; i++) for(int j = 1; j <= M; j++) if(mp[i][j] == ‘W‘) DFS(i, j), ans++; printf("%d\n", ans); }
原文：http://www.cnblogs.com/pealicx/p/6286103.html