1.方格迷宫

题目

链接： 4943. 方格迷宫 - AcWing题库
给定一个 n 行 m 列的方格矩阵。

行从上到下依次编号为 1∼n，列从左到右依次编号为 1∼m。

第 i 行第 j 列的方格表示为 (i,j)。

矩阵中的方格要么是空地（用 . 表示），要么是陷阱（用 # 表示）。

初始时，你位于方格 (x1,y1)，你需要前往方格 (x2,y2)。

每次移动，你可以任选上、下、左、右四个方向之一，并沿该方向移动 1∼k 步。

从一个方格移动至相邻方格视为一步。

但是，你要保证在你的移动过程中不能走出矩阵，也不能进入陷阱方格。

请你计算从方格 (x1,y1) 移动至方格 (x2,y2)，所需要的最少移动次数。

保证方格 (x1,y1) 和方格 (x2,y2) 都是空地。

方格 (x1,y1) 和方格 (x2,y2) 可能是同一个方格。

注意：注意区分本题中移动次数与移动步数的区别。

输入格式

第一行包含三个整数 n,m,k 。

接下来 n 行，每行包含 m 个字符，其中第 i 行第 j 个字符，要么是 .，表示方格 (i,j) 是空地；要么是 #，表示方格 (i,j) 是陷阱。

最后一行包含四个整数 x1,y1,x2,y2。

输出格式

一个整数，表示所需要的最少移动次数。

如果无法从方格 (x1,y1) 移动至方格 (x2,y2)，则输出 -1。

数据范围

前 6 个测试点满足 1≤n,m≤10。
所有测试点满足 1≤n,m,k≤1000，1≤x1,x2≤n，1≤y1,y2≤m。

输入样例1：
```
3 4 4
....
###.
....
1 1 3 1
```
输出样例1：
```
3
```
输入样例2：
```
3 4 1
....
###.
....
1 1 3 1
```
输出样例2：
```
8
```
输入样例3：
```
2 2 1
.#
#.
1 1 2 2
```
输出样例3：
```
-1
```

第一次 AC 5/21

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

typedef pair<int,int> PII;

const int N =1010;

int n,m,k;
int d[N][N];
char g[N][N];
int x1,jj,x2,y2;
int dx[4]={0,0,-1,1},dy[4]={1,-1,0,0};

void bfs()
{
    memset(d,-1,sizeof d);
    
    d[x1][jj]=0;
    
    queue<PII> q;
    q.push({x1,jj});
    
    while(q.size())
    {
        auto t=q.front();
        q.pop();
        
        for(int i=0;i<4;i++)
        {
            for(int j=1;j<=k;j++)
            {
                int x=t.first+dx[i]*j,y=t.second+dy[i]*j;  //题中是 1~k ，不是 k，开始审题没注意
                if(d[x][y]==-1&&x>=1&&y>=1&&x<=n&&y<=m&&g[x][y]!='#')
                {
                    d[x][y]=d[t.first][t.second]+1;
                    q.push({x,y});
                }
            }
            
        }
    }
    cout<<d[x2][y2];
}

int main()
{
    int n,m,k;
    cin>>n>>m>>k;
    
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>g[i][j];
            
    cin>>x1>>jj>>x2>>y2;
    
    if(x1==x2&&jj==y2)
    {
        cout<<0;
        return 0;
    }
            
    bfs();
    
    return 0;
}

第二次模拟题解样例过不了

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

typedef pair<int,int> PII;

const int N =1010;

int n,m,k;
int d[N][N];
char g[N][N];
int x1,y1,x2,y2;
int dx[4]={0,0,-1,1},dy[4]={1,-1,0,0};

int bfs()
{
    memset(d,-1,sizeof d);
    
    d[x1][y1]=0;
    
    queue<PII> q;
    q.push({x1,y1});
    
    while(q.size())
    {
        auto t=q.front();
        q.pop();
        
        for(int i=0;i<4;i++)
        {
            for(int j=1;j<=k;j++)
            {
                int x=t.first+dx[i]*j,y=t.second+dy[i]*j;
                
                if(g[x][y]=='#') break; //这个方向上已经遇到陷阱了，k++，肯定也过不去
                
                if(d[x][y]==-1&&x>=1&&y>=1&&x<=n&&y<=m&&g[x][y]=='.')
                {
                    d[x][y]=d[t.first][t.second]+1;
                    q.push({x,y});
                }
                
                else if(x>n||y>m||x<1||y<1) break;   //
                else if(d[x][y]<=d[t.first][t.second]) break;
            }
            
        }
    }
    return d[x2][y2];
}

int main()
{
    int n,m,k;
    cin>>n>>m>>k;
    
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>g[i][j];
            
    cin>>x1>>y1>>x2>>y2;
    
    if(x1==x2&&y1==y2)
    {
        cout<<0;
        return 0;
    }
            
    cout<<bfs();
    
    return 0;
}

不知道哪里错了，摸索中

正确题解

1.如果碰到陷阱立刻停止，加if (g [ x ] [ y ] == '#') break;
2.如果越过边界立刻停止，加else if (x < 1 || x > n || y < 1 || y > m) break;
3.为避免重复计算带来超时，加else if (d [ x ] [ y ] <= d [ t.first ] [t .second]) break;

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

typedef pair<int, int> PII;
int n, m, k,x1,x2,y1,y2;

const int N = 1010;

char g[N][N];

int d[N][N];

int bfs()
{
    queue<PII>q;

    memset(d, -1, sizeof d);
    d[x1][y1] = 0;

    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    if(x1 == x2 && y2 == y1) return 0 && puts("0");

    q.push({x1,y1});

    while(q.size())
    {
        auto t = q.front();
        q.pop();
        for(int i = 0; i < 4; i ++ )
        {
            for (int j = 1; j <= k; j ++ )
            {
                int x = t.first + j*dx[i], y = t.second + j*dy[i];  //k表步数
                if (g[x][y] == '#') break;
                if(x>=1 && x <= n && y >= 1 && y <= m && g[x][y] == '.' && d[x][y] == -1)
                {
                    d[x][y] = d[t.first][t.second] + 1;
                    q.push({x,y});
                }
                else if (x < 1 || x > n || y < 1 || y > m) break;
                else if (d[x][y] <= d[t.first][t.second]) break;
            }
        }
    }
    return d[x2][y2];
}

int main()
{
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i ++ ) scanf("%s", g[i] + 1);

    cin >> x1 >> y1 >> x2 >> y2;
    cout << bfs() << endl;

    return 0;
}

反思
1. 万能头不能和 y1 共存，以后使用 abcd 来代替
2. 学会剪枝，特殊情况，使用break 来缩短时间
3. 编号坐标注意是从 0 开始还是 1 开始

2.字符串删减

题目

链接： 3768. 字符串删减 - AcWing题库
给定一个由 n 个小写字母构成的字符串。

现在，需要删掉其中的一些字母，使得字符串中不存在连续三个或三个以上的 x。

请问，最少需要删掉多少个字母？

如果字符串本来就不存在连续的三个或三个以上 x，则无需删掉任何字母。

输入格式

第一行包含整数 n。

第二行包含一个长度为 n 的由小写字母构成的字符串。

输出格式

输出最少需要删掉的字母个数。

数据范围

3≤n≤100

输入样例1：
```
6
xxxiii
```
输出样例1：
```
1
```
输入样例2：
```
5
xxoxx
```
输出样例2：
```
0
```
输入样例3：
```
10
xxxxxxxxxx
```
输出样例3：
```
8
```

第一次 AC 0%

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

const int N=110;
char a[N];

int main()
{
    int n;
    cin>>n;
    
    int cnt=0;
    
    for(int i=0;i<n;i++)
        cin>>a[i];
    
    int j=0;
    for(int i=0;i<n;i++)
    {
        while(a[i]=='x')
        {
            i++;
        }
        cnt+=max(0,i-j-3); //应该是 -2，因为如果 xxx，会变成 xx ,-1，手动
        j=i;  //j应该等于 i+1 才正确
    }
    
    cout<<cnt;
    
    return 0;
}

边界处理问题

第二次 AC 100%

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

const int N=110;
char a[N];

int main()
{
    int n;
    cin>>n;
    
    int cnt=0;
    
    for(int i=0;i<n;i++)
        cin>>a[i];
    
    int j=0;
    for(int i=0;i<n;i++)
    {
        while(a[i]=='x')
        {
            i++;
        }
        cnt+=max(0,i-j-2);
        j=i+1;  //这两个边界改了之后就可以了
    }
    
    cout<<cnt;
    
    return 0;
}