bfs做法

#include<bits/stdc++.h>
using namespace std;

struct manCow
{
    int x;//坐标
    int deep;//时间
};
queue<manCow> q;
bool flags[100010];//标记该点是否走过，否则会MLE
void bfs(int x, int y)
{
    manCow f;
    f.x = x;
    f.deep = 0;
    flags[f.x] = 1;  
    q.push(f);//入队
    while(!q.empty())
    {
        f = q.front();
        q.pop();
        if(f.x == y)//退出条件
        {
            cout << f.deep << endl;
            return;
      }

        manCow fn;
        fn.deep = f.deep + 1;//更新时间
        if(f.x > y)
        {
            fn.x = f.x - 1;
            if(fn.x >= 0 && fn.x <= 100000)//一定要有， 否则RE
            {
                if(flags[fn.x] != 1)
                {
                    flags[fn.x] = 1;
                  q.push(fn);
              }
            }
        }
        else
        {
            for(int i = 0;i < 3;i++)
            {
                if(i == 0)
                fn.x = f.x + 1;
                if(i == 1)
                fn.x = f.x - 1;
                if(i == 2)
                fn.x = 2 * f.x;//新的坐标
                if(fn.x >= 0 && fn.x <= 100000)
                {
                    if(flags[fn.x] != 1)
                    {
                        flags[fn.x] = 1;
                      q.push(fn);
                  }
                }
            }
      }
    }
}

int main()
{
    int fx, cx;
    cin >> fx >> cx;

    bfs(fx, cx);


    return 0;
}

Acwing.1100抓住那头牛
用bfs如何做？
下附MLE代码

#include<bits/stdc++.h>
using namespace std;

struct manCow
{
    int x;
    int deep;
};
queue<manCow> q;

void bfs(int x, int y)
{
    manCow f;
    f.x = x;
    f.deep = 0;
    q.push(f);

    while(!q.empty())
    {
        f = q.front();

        if(f.x == y)
        {
            cout << f.deep << endl;
            return;
      }

        manCow fn;
        fn.deep = f.deep + 1;
        if(f.x > y)
        {
            fn.x = f.x - 1;
            q.push(fn);
        }
        else
        {
            for(int i = 0;i < 3;i++)
            {
                if(i == 0)
                fn.x = f.x + 1;
                if(i == 1)
                fn.x = f.x - 1;
                if(i == 2)
                fn.x = 2 * f.x;
                q.push(fn);
            }
      }

        q.pop();
    }
}

int main()
{
    int fx, cx;
    cin >> fx >> cx;

    bfs(fx, cx);


    return 0;
}

bfs 做法

#include<bits/stdc++.h>
using namespace std;

int n, m;
char field[101][101];
int ans = 0;
struct point
{
    int x;
    int y;
};
queue<point> q; 

void bfs(int x, int y)
{
    point p1;
    p1.x = x;
    p1.y = y;
    q.push(p1);
    while(!q.empty())
    {
      for(int i = -1;i <= 1;i++)
      {
            for(int j = -1;j <= 1;j++)
            {
                int ny = q.front().y + j;
                int nx = q.front().x + i;
                if(nx >= 0 && nx < n
                   && ny >= 0 && ny < m
                     && field[nx][ny] == 'W')
                {
                    field[nx][ny] = '.';
                    point p2;
                    p2.x = nx;
                    p2.y = ny;
                  q.push(p2);
                }
            }
      }
      q.pop();
    }
}


int main()
{
    cin >> n >> m;
    for(int i = 0;i < n;i++)
    {
        for(int j = 0;j < m;j++)
        {   
            cin >> field[i][j];
        }
    }

    for(int i = 0;i < n;i++)
    {
        for(int j = 0;j < m;j++)
        {
            if(field[i][j] == 'W')
            {
                bfs(i, j);
                ans++;
            }
        }
    }
    cout << ans << endl;


    return 0;
}

dfs做法

#include<bits/stdc++.h>
using namespace std;

int n, m;
char field[101][101];
int ans = 0;

void dfs(int x, int y)
{
      for(int i = -1;i <= 1;i++)
      {
            for(int j = -1;j <= 1;j++)
            {
                int ny = y + j;
                int nx = x + i;
                if(nx >= 0 && nx < n
                   && ny >= 0 && ny < m
                     && field[nx][ny] == 'W')
                {
                    field[nx][ny] = '.';
                    dfs(nx, ny);
                }
            }
      }
      return;
}


int main()
{
    cin >> n >> m;
    for(int i = 0;i < n;i++)
    {
        for(int j = 0;j < m;j++)
        {   
            cin >> field[i][j];
        }
    }
    for(int i = 0;i < n;i++)
    {
        for(int j = 0;j < m;j++)
        {   
            if(field[i][j] == 'W')
            {
                dfs(i, j);
                ans++;
            }
        }
    }

    cout << ans << endl;


    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 20123;
struct hulk
{
    int j;
    int x;
};
int num[10001] = {0};
hulk o[10001][101];//存储n,m,个人比较喜用结构体
int main()
{
    int n, m, st;
    cin >> n >> m;

    for(int i = 1;i <= n;i++)
    {
        for(int j = 0;j < m;j++)
        {
            cin >> o[i][j].j >> o[i][j].x;
            if(o[i][j].j == 1)
                num[i]++;//统计每层梯子数量
        }
    }

    cin >> st;

    int ans = 0;
  for(int i = 1;i <= n;i++)
  {
        ans += o[i][st].x;//密钥
        int tmp = o[i][st].x % num[i];//利用周期性，x取模每层的梯子数，不然5个T
            if(!tmp)
            {
                tmp = num[i];//余数为0特殊处理
            }
            for(int j = st;;j++)//循环找即可
            {
                if(o[i][j].j == 1)
                    tmp--;
                if(!tmp)
                {
                  st = j;//更新st
                  break;
              }
              if(j == m - 1)
                j = -1;
            }
    }
    cout << ans % N<< endl;//取模不要忘， wo因为这个调了半小时
    return 0;
}

1、首先说前面相乘是什么情况–GGGHGGGG，比如这样的情况的牛，左边取1头G右边取1头加上中间H，就组成了GHG，这就是一个孤独的牛，需要删掉，然后右边取到GGGG都是一样，可以组成孤独的牛，然后在左边取两头，右边全部取，这样就是两个数的乘积的结果，
2、然后加上左边 - 1的长度，需要满足长度是3，所以左边是GGGH，左边不同的牛长度是3，你不能直接就取3，要留出一个组成跟中间点组成GH来达到长度是3，所以就是左边剩下两头G，取一头跟两头可以组成两种情况 ，就有G+GH ， GG + GH，这样两种情况就是左边长度 - 1；
3、右边同理

import java.util.*;
import java.io.*;
public class Main{
    static int N = 500010;
    static char[] g = new char[N];//存储所有牛
    public static void main(String[] args)throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter wt = new PrintWriter(new OutputStreamWriter(System.out));
        Scanner scan = new Scanner(System.in);
        int n = Integer.parseInt(bf.readLine());//输入n
        g = bf.readLine().toCharArray();//输入所有牛

        long res = 0;
        for (int i = 0 ; i < n ; i ++){  //枚举所有牛
            int lhs = 0; //当前这头牛的左边不同的连续的牛
            //i > 0保证了左边这头牛，如果是=0，那么左边没有牛
            //并且左边跟他不相等的数的长度
            if (i > 0 && g[i] != g[i - 1]){   
                lhs ++;
                //然后看左边最长不超过边界的最长的不同的牛 
                for (int j = i - 2;j >= 0 && g[j] != g[i]; j -- ) lhs ++;
            }
            int rhs = 0;//当前这头牛的右边不同的连续的牛
            //i + 1 < n 保证了右边这头牛，如果是>n，那么右边超过边界没有牛
            //并且右边跟他不相等的数的长度
            if (i + 1 < n && g[i + 1] != g[i]){
                rhs ++;
                //然后看右边最长不超过边界的最长的不同的牛 
                for (int j = i + 2 ; j < n  && g[j] != g[i]; j ++) rhs ++;
            }
            //每次累加所有的牛的应该扔掉的孤独照片
            //左边跟右边的所有点都可以跟中间当前点组成
            //（左边长度*右边长度 + 左边的长度 - 1 + 右边的长度 - 1）
            ///为什么左边减1呢，因为长度最低是3，所以要留出 一个当前点跟左边一个点，
            //然后跟左边其他点组成3以上的长度，右边同理
            res += (long)lhs * rhs + (long)Math.max(0,lhs - 1) + (long)Math.max(0,rhs - 1);
        }
        System.out.println(res);
        wt.flush();
    }
}

1、首先说前面相乘是什么情况–GGGHGGGG，比如这样的情况的牛，左边取1头G右边取1头加上中间H，就组成了GHG，这就是一个孤独的牛，需要删掉，然后右边取到GGGG都是一样，可以组成孤独的牛，然后在左边取两头，右边全部取，这样就是两个数的乘积的结果，
2、然后加上左边 - 1的长度，需要满足长度是3，所以左边是GGGH，左边不同的牛长度是3，你不能直接就取3，要留出一个组成跟中间点组成GH来达到长度是3，所以就是左边剩下两头G，取一头跟两头可以组成两种情况 ，就有G+GH ， GG + GH，这样两种情况就是左边长度 - 1；
3、右边同理

import java.util.*;
import java.io.*;
public class Main{
    static int N = 500010;
    static char[] g = new char[N];//存储所有牛
    public static void main(String[] args)throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter wt = new PrintWriter(new OutputStreamWriter(System.out));
        Scanner scan = new Scanner(System.in);
        int n = Integer.parseInt(bf.readLine());//输入n
        g = bf.readLine().toCharArray();//输入所有牛

        long res = 0;
        for (int i = 0 ; i < n ; i ++){  //枚举所有牛
            int lhs = 0; //当前这头牛的左边不同的连续的牛
            //i > 0保证了左边这头牛，如果是=0，那么左边没有牛
            //并且左边跟他不相等的数的长度
            if (i > 0 && g[i] != g[i - 1]){   
                lhs ++;
                //然后看左边最长不超过边界的最长的不同的牛 
                for (int j = i - 2;j >= 0 && g[j] != g[i]; j -- ) lhs ++;
            }
            int rhs = 0;//当前这头牛的右边不同的连续的牛
            //i + 1 < n 保证了右边这头牛，如果是>n，那么右边超过边界没有牛
            //并且右边跟他不相等的数的长度
            if (i + 1 < n && g[i + 1] != g[i]){
                rhs ++;
                //然后看右边最长不超过边界的最长的不同的牛 
                for (int j = i + 2 ; j < n  && g[j] != g[i]; j ++) rhs ++;
            }
            //每次累加所有的牛的应该扔掉的孤独照片
            //左边跟右边的所有点都可以跟中间当前点组成
            //（左边长度*右边长度 + 左边的长度 - 1 + 右边的长度 - 1）
            ///为什么左边减1呢，因为长度最低是3，所以要留出 一个当前点跟左边一个点，
            //然后跟左边其他点组成3以上的长度，右边同理
            res += (long)lhs * rhs + (long)Math.max(0,lhs - 1) + (long)Math.max(0,rhs - 1);
        }
        System.out.println(res);
        wt.flush();
    }
}

1、首先说前面相乘是什么情况–GGGHGGGG，比如这样的情况的牛，左边取1头G右边取1头加上中间H，就组成了GHG，这就是一个孤独的牛，需要删掉，然后右边取到GGGG都是一样，可以组成孤独的牛，然后在左边取两头，右边全部取，这样就是两个数的乘积的结果，
2、然后加上左边 - 1的长度，需要满足长度是3，所以左边是GGGH，左边不同的牛长度是3，你不能直接就取3，要留出一个组成跟中间点组成GH来达到长度是3，所以就是左边剩下两头G，取一头跟两头可以组成两种情况 ，就有G+GH ， GG + GH，这样两种情况就是左边长度 - 1；
3、右边同理

import java.util.*;
import java.io.*;
public class Main{
    static int N = 500010;
    static char[] g = new char[N];//存储所有牛
    public static void main(String[] args)throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter wt = new PrintWriter(new OutputStreamWriter(System.out));
        Scanner scan = new Scanner(System.in);
        int n = Integer.parseInt(bf.readLine());//输入n
        g = bf.readLine().toCharArray();//输入所有牛

        long res = 0;
        for (int i = 0 ; i < n ; i ++){  //枚举所有牛
            int lhs = 0; //当前这头牛的左边不同的连续的牛
            //i > 0保证了左边这头牛，如果是=0，那么左边没有牛
            //并且左边跟他不相等的数的长度
            if (i > 0 && g[i] != g[i - 1]){   
                lhs ++;
                //然后看左边最长不超过边界的最长的不同的牛 
                for (int j = i - 2;j >= 0 && g[j] != g[i]; j -- ) lhs ++;
            }
            int rhs = 0;//当前这头牛的右边不同的连续的牛
            //i + 1 < n 保证了右边这头牛，如果是>n，那么右边超过边界没有牛
            //并且右边跟他不相等的数的长度
            if (i + 1 < n && g[i + 1] != g[i]){
                rhs ++;
                //然后看右边最长不超过边界的最长的不同的牛 
                for (int j = i + 2 ; j < n  && g[j] != g[i]; j ++) rhs ++;
            }
            //每次累加所有的牛的应该扔掉的孤独照片
            //左边跟右边的所有点都可以跟中间当前点组成
            //（左边长度*右边长度 + 左边的长度 - 1 + 右边的长度 - 1）
            ///为什么左边减1呢，因为长度最低是3，所以要留出 一个当前点跟左边一个点，
            //然后跟左边其他点组成3以上的长度，右边同理
            res += (long)lhs * rhs + (long)Math.max(0,lhs - 1) + (long)Math.max(0,rhs - 1);
        }
        System.out.println(res);
        wt.flush();
    }
}

1、首先说前面相乘是什么情况–GGGHGGGG，比如这样的情况的牛，左边取1头G右边取1头加上中间H，就组成了GHG，这就是一个孤独的牛，需要删掉，然后右边取到GGGG都是一样，可以组成孤独的牛，然后在左边取两头，右边全部取，这样就是两个数的乘积的结果，
2、然后加上左边 - 1的长度，需要满足长度是3，所以左边是GGGH，左边不同的牛长度是3，你不能直接就取3，要留出一个组成跟中间点组成GH来达到长度是3，所以就是左边剩下两头G，取一头跟两头可以组成两种情况 ，就有G+GH ， GG + GH，这样两种情况就是左边长度 - 1；
3、右边同理

import java.util.*;
import java.io.*;
public class Main{
    static int N = 500010;
    static char[] g = new char[N];//存储所有牛
    public static void main(String[] args)throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter wt = new PrintWriter(new OutputStreamWriter(System.out));
        Scanner scan = new Scanner(System.in);
        int n = Integer.parseInt(bf.readLine());//输入n
        g = bf.readLine().toCharArray();//输入所有牛

        long res = 0;
        for (int i = 0 ; i < n ; i ++){  //枚举所有牛
            int lhs = 0; //当前这头牛的左边不同的连续的牛
            //i > 0保证了左边这头牛，如果是=0，那么左边没有牛
            //并且左边跟他不相等的数的长度
            if (i > 0 && g[i] != g[i - 1]){   
                lhs ++;
                //然后看左边最长不超过边界的最长的不同的牛 
                for (int j = i - 2;j >= 0 && g[j] != g[i]; j -- ) lhs ++;
            }
            int rhs = 0;//当前这头牛的右边不同的连续的牛
            //i + 1 < n 保证了右边这头牛，如果是>n，那么右边超过边界没有牛
            //并且右边跟他不相等的数的长度
            if (i + 1 < n && g[i + 1] != g[i]){
                rhs ++;
                //然后看右边最长不超过边界的最长的不同的牛 
                for (int j = i + 2 ; j < n  && g[j] != g[i]; j ++) rhs ++;
            }
            //每次累加所有的牛的应该扔掉的孤独照片
            //左边跟右边的所有点都可以跟中间当前点组成
            //（左边长度*右边长度 + 左边的长度 - 1 + 右边的长度 - 1）
            ///为什么左边减1呢，因为长度最低是3，所以要留出 一个当前点跟左边一个点，
            //然后跟左边其他点组成3以上的长度，右边同理
            res += (long)lhs * rhs + (long)Math.max(0,lhs - 1) + (long)Math.max(0,rhs - 1);
        }
        System.out.println(res);
        wt.flush();
    }
}

1、首先说前面相乘是什么情况–GGGHGGGG，比如这样的情况的牛，左边取1头G右边取1头加上中间H，就组成了GHG，这就是一个孤独的牛，需要删掉，然后右边取到GGGG都是一样，可以组成孤独的牛，然后在左边取两头，右边全部取，这样就是两个数的乘积的结果，
2、然后加上左边 - 1的长度，需要满足长度是3，所以左边是GGGH，左边不同的牛长度是3，你不能直接就取3，要留出一个组成跟中间点组成GH来达到长度是3，所以就是左边剩下两头G，取一头跟两头可以组成两种情况 ，就有G+GH ， GG + GH，这样两种情况就是左边长度 - 1；
3、右边同理

import java.util.*;
import java.io.*;
public class Main{
    static int N = 500010;
    static char[] g = new char[N];//存储所有牛
    public static void main(String[] args)throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter wt = new PrintWriter(new OutputStreamWriter(System.out));
        Scanner scan = new Scanner(System.in);
        int n = Integer.parseInt(bf.readLine());//输入n
        g = bf.readLine().toCharArray();//输入所有牛

        long res = 0;
        for (int i = 0 ; i < n ; i ++){  //枚举所有牛
            int lhs = 0; //当前这头牛的左边不同的连续的牛
            //i > 0保证了左边这头牛，如果是=0，那么左边没有牛
            //并且左边跟他不相等的数的长度
            if (i > 0 && g[i] != g[i - 1]){   
                lhs ++;
                //然后看左边最长不超过边界的最长的不同的牛 
                for (int j = i - 2;j >= 0 && g[j] != g[i]; j -- ) lhs ++;
            }
            int rhs = 0;//当前这头牛的右边不同的连续的牛
            //i + 1 < n 保证了右边这头牛，如果是>n，那么右边超过边界没有牛
            //并且右边跟他不相等的数的长度
            if (i + 1 < n && g[i + 1] != g[i]){
                rhs ++;
                //然后看右边最长不超过边界的最长的不同的牛 
                for (int j = i + 2 ; j < n  && g[j] != g[i]; j ++) rhs ++;
            }
            //每次累加所有的牛的应该扔掉的孤独照片
            //左边跟右边的所有点都可以跟中间当前点组成
            //（左边长度*右边长度 + 左边的长度 - 1 + 右边的长度 - 1）
            ///为什么左边减1呢，因为长度最低是3，所以要留出 一个当前点跟左边一个点，
            //然后跟左边其他点组成3以上的长度，右边同理
            res += (long)lhs * rhs + (long)Math.max(0,lhs - 1) + (long)Math.max(0,rhs - 1);
        }
        System.out.println(res);
        wt.flush();
    }
}