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