目录

1 flood fill

1.Lake Counting

2.The Castle

3.山峰和山谷

2最短路模型

1.迷宫问题

2.武士风度的牛

3.抓住那头牛

1 flood fill

1.Lake Counting

信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)

#include
using namespace std;
#define x first
#define y second
typedef pair pii;
const int N=115;
int n,m,cnt=0;
char g[N][N];
bool st[N][N];
pii q[N*N];
void bfs(int sx,int sy)
{
    int hh=0,tt=0;
    q[0]={sx,sy};
    st[sx][sy]=true;
    while(hh<=tt)
    {
        auto t=q[hh++];
        for(int i=t.x-1;i<=t.x+1;i++)//因为求八个周围的，则循环枚举两层即可
            for(int j=t.y-1;j<=t.y+1;j++)
            {
               if(i<0||i>=n||j<0||j>=m) continue;//假如越界则continue
               if(st[i][j]) continue;//假如标记过则continue
               if(g[i][j]=='.') continue;//假如是干燥的则continue
               st[i][j]=true;//标记这个点被标记过
               q[++tt]={i,j};//把这个积水放进队列用，以后用他来更新其他的积水
            }
    }
}
int main()
{
  cin>>n>>m;
  for(int i=0;i>g[i];
  for(int i=0;i 
2.The Castle 
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
 
#include
using namespace std;
#define x first
#define y second
typedef pair pii;
const int N=55;
int n,m,cnt=0,ans=0;
int g[N][N];
bool st[N][N];
pii q[N*N];
int dx[4]={0,-1,0,1},dy[4]={-1,0,1,0};//按照题目的方向西北东南的方向
int bfs(int sx,int sy)
{
    int hh=0,tt=0;
    q[0]={sx,sy};
    st[sx][sy]=true;
    while(hh<=tt)
    {
        auto t=q[hh++];//取出队头
       for(int i=0;i<4;i++)//枚举西北东南四个方向
            {
                int a=t.x+dx[i],b=t.y+dy[i];//下一步
               if(a<0||a>=n||b<0||b>=m) continue;//假如越界则continue
               if(st[a][b]) continue;//假如标记过则continue
               if((g[t.x][t.y]>>i)&1) continue;//假如是墙的话则continue
               st[a][b]=true;//标记这个点被标记过
               q[++tt]={a,b};//把这个点放进队列用，以后用他来更新其他的房间
            }
    }
   return tt+1;//返回房间数量
}
int main()
{
  cin>>n>>m;
  for(int i=0;i>g[i][j];
  for(int i=0;i 
3.山峰和山谷 
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
 
#include
using namespace std;
#define x first
#define y second
typedef pair pii;
const int N=1e3+10;
int n;
int g[N][N];
bool st[N][N];
pii q[N*N];
int bfs(int sx,int sy)
{
    int hh=0,tt=0;
    bool up=false,low=false;//用来记录是不是山峰或者山谷
    st[sx][sy]=true;
    q[0]={sx,sy};
    while(hh<=tt)
    {
        auto t=q[hh++];
        //因为是要周围八个方向，所以用枚举的方法
        for(int i=t.x-1;i<=t.x+1;i++)
            for(int j=t.y-1;j<=t.y+1;j++)
        {
            if(i<0||i>=n||j<0||j>=n) continue;//假如越界
            if(g[i][j]>g[t.x][t.y]) low=true;//假如是山谷
            else if(g[i][j]>n;
   for(int i=0;i>g[i][j];
   for(int i=0;i 
2最短路模型 
1.迷宫问题 
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
 
#include
using namespace std;
#define x first
#define y second
typedef pair pii;
const int N=10;
int n;
int g[N][N];
bool st[N][N];//标记那个点被走过了
pii q[N*N],pre[N][N];//pre用来记录某个点的上一步
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
void bfs(int sx,int sy)
{
    int hh=0,tt=0;
    st[sx][sy]=true;
    q[0]={sx,sy};
    pre[sx][sy]={0,0};
    while(hh<=tt)
    {
        auto t=q[hh++];
       for(int i=0;i<4;i++)//枚举四个方向
       {
           int a=t.x+dx[i],b=t.y+dy[i];
           if(a<0||a>=n||b<0||b>=n) continue;//假如越界
           if(g[a][b]) continue;//假如是墙，不能走
           if(st[a][b]) continue;//假如之前走过这个点
           q[++tt]={a,b};
           st[a][b]=true;
           pre[a][b]=t;//标记这个点由t转移过来的
        }
    }
}
int main()
{
    n=5;
   for(int i=0;i>g[i][j];
   bfs(n-1,n-1);//倒序求最短路
   pii end(0,0);//正向输出路径
   while(1)
   {
       printf("(%d, %d)n",end.x,end.y);
       if(end.x==n-1&&end.y==n-1) break;
       end=pre[end.x][end.y];
   }
   return 0;
}
 
2.武士风度的牛 
188. 武士风度的牛 - AcWing题库
 
#include
using namespace std;
#define x first
#define y second
typedef pair pii;
const int N=160;
int n,m;
char g[N][N];
int dist[N][N];//记录吗，每个点到起点的步数
pii q[N*N];
int dx[]={-1,1,2,2,1,-1,-2,-2},dy[]={2,2,1,-1,-2,-2,-1,1};//题目中的八个方向
int bfs(int sx,int sy,int ex,int ey)
{
    int hh=0,tt=0;
    q[0]={sx,sy};
    memset(dist,-1,sizeof dist);
    dist[sx][sy]=0;
    while(hh<=tt)
    {
        auto t=q[hh++];
       for(int i=0;i<8;i++)//枚举八个方向
       {
           int a=t.x+dx[i],b=t.y+dy[i];
           if(a<0||a>=n||b<0||b>=m) continue;//假如越界
           if(g[a][b]=='*') continue;//假如是障碍，不能走
           if(dist[a][b]!=-1) continue;//假如之前已经更新过这个点
           q[++tt]={a,b};
           dist[a][b]=dist[t.x][t.y]+1;//则步数+1
        }
    }
    return dist[ex][ey];//返回到终点的步数
}
int main()
{
   cin>>m>>n;
   int sx,sy,ex,ey;
   for(int i=0;i>g[i][j];
       if(g[i][j]=='K') sx=i,sy=j;//标记起点
       if(g[i][j]=='H') ex=i,ey=j;//标记终点
   }
   cout< 
3.抓住那头牛 
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
 
#include
using namespace std;
const int N=2e5+10;
int n,k;
int dist[N];//记录每个点到起点的步数
int q[N];
int bfs()
{
    int hh=0,tt=0;
    q[0]=n;
    memset(dist,-1,sizeof dist);
    dist[n]=0;
    while(hh<=tt)
    {
        int t=q[hh++];
        if(t==k) return dist[k];//返回到起点的步数
        if(t+1=0&&dist[t-1]==-1)//第二种情况走，且该位置没有被走过
        {
            dist[t-1]=dist[t]+1;//则该点距离+1
            q[++tt]=t-1;//将该点放进队列中
        }
        if(2*t>n>>k;
   cout<