训练[2]-DFS

题目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,

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 = ;

char S[MAXN];

int T, N;

int main ()

{

    scanf("%d", &T);

    getchar();

    while(T--)

    {

        gets(S + );

        N = strlen(S + );

        if(S[] == ' ')//第一种情况

        {

            printf("Yes\n");

            continue;

        }

        stack<char>st;

        for(int i = ; 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 ;

}

题目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 = ;

char mp[MAXN][MAXN];

int N, M;

void DFS(int x, int y)

{

    mp[x][y] = '.';

    for(int i = -; i <= ; i++)

        for(int j = -; j <= ; j++)

            if(mp[x+i][y+j] == 'W')

                DFS(x+i, y+j);

}

int main ()

{

    int ans = ;

    scanf("%d%d", &N, &M);

    for(int i = ; i <= N; i++)

        scanf("%s", mp[i] + );

    for(int i = ; i <= N; i++)

        for(int j = ; j <= M; j++)

            if(mp[i][j] == 'W') DFS(i, j), ans++;

    printf("%d\n", ans);

}

巴特西

训练[2]-DFS

最新文章

热门文章