# 【深基15.习9】验证栈序列
## 题目描述
给出两个序列 pushed 和 poped 两个序列，其取值从 1 到 n(n<=100000)。已知入栈序列是 pushed，如果出栈序列有可能是 poped，则输出 `Yes`，否则输出 `No`。为了防止骗分，每个测试点有多组数据。
## 输入格式
第一行一个整数 q，询问次数。
接下来 q个询问，对于每个询问：
第一行一个整数 n?表示序列长度；
第二行 n?个整数表示入栈序列；
第三行 n?个整数表示出栈序列；
## 输出格式
对于每个询问输出答案。
## 样例 #1
### 样例输入 #1
```
2
5
1 2 3 4 5
5 4 3 2 1
4
1 2 3 4
2 4 1 3
```
### 样例输出 #1
```
Yes
No
```
看到这道题我的第一想法是只要看第一个序列是不是第二个序列的倒序就行了，写出来一上交全错了。
看了一下题解才明白倒序只是一种出栈可能，举个例子吧：
1 2 3
1 2 3
这个是对的，当1 2 3入栈的时候立马就出栈，那么出栈顺序就是1 2 3了。
于是我们只要在入栈的过程中加一个循环语句用来判断什么时候该出栈就行了
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main()
{
int x,y,z,d,k=0,g;
int a[100000];
int b[100000];
int c[100000];
cin>>d;
for(x=0;x<d;x++)
{
k=0;z=0;
cin>>y;
for(g=0;g<y;g++)
cin>>a[g]; //接收入栈序列
for(g=0;g<y;g++)
cin>>b[g]; //接收出栈序列
for(g=0;g<y;g++)
{
c[k]=a[g]; //模拟入栈
while(c[k]==b[z]&&k>=0&&z<y)//当栈顶部的数和出栈序列相同时出栈，直到与出栈序列不同
{
k--;z++;
}
k++;
}
if(k==0)
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
return 0;
}
# 迷宫
## 题目描述
给定一个 N*M方格的迷宫，迷宫里有 T处障碍，障碍处不可通过。
在迷宫中移动有上下左右四种方式，每次只能移动一个方格。数据保证起点上没有障碍。
给定起点坐标和终点坐标，每个方格最多经过一次，问有多少种从起点坐标到终点坐标的方案。
## 输入格式
第一行为三个正整数 N,M,T，分别表示迷宫的长宽和障碍总数。
第二行为四个正整数 SX,SY,FX,FY，SX,SY?代表起点坐标，FX,FY?代表终点坐标。
接下来 T?行，每行两个正整数，表示障碍点的坐标。
## 输出格式
输出从起点坐标到终点坐标的方案总数。
## 样例 #1
### 样例输入 #1
```
2 2 1
1 1 2 2
1 2
```
### 样例输出 #1
```
1
```
## 提示
对于 100%?的数据，1 <=?N,M <=?5，1 <=?T <=?10，1 <=?SX,FX <=?n，1 <=?SY,FY <=?m。
这道题的解题要用到dfs（深度搜索），是一个dfs的简单题。
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int g[6][6]; //模拟迷宫
int j[6][6]; //为迷宫打标记
int a,b,c,d,k;
int l[4][2]={{0,1},{1,0},{-1,0},{0,-1}}; //用于向四个方向走
int cz(int x,int y)
{
int tx,ty,n;
if(x==c&&y==d) //当到达目的地时停止
{
k++; //k自加
return 0;
}
for(n=0;n<4;n++)
{
tx=x+l[n][0]; //向下一个方向走
ty=y+l[n][1];
if(tx<1||ty<1||tx>a||ty>b) //限定迷宫范围
continue;
if(g[tx][ty]!=1&&j[tx][ty]!=1) //防止走重复的路并在障碍物前停下
{
j[tx][ty]=1; //为当前位置标记
cz(tx,ty); //走下一步
j[tx][ty]=0; //撤销标记
}
}
return 0;
}
int main()
{
int x1,x,y1,z,e,f;
scanf("%d%d%d",&a,&b,&z);
scanf("%d%d%d%d",&e,&f,&c,&d);
for(x1=1;x1<=a;x1++)
for(y1=1;y1<=b;y1++)
{
g[x1][y1]=0; //0为没有障碍物
}
for(x=1;x<=z;x++)
{
scanf("%d%d",&x1,&y1); //为迷宫设障碍物，1为障碍物
g[x1][y1]=1;
}
j[e][f]=1; //为起点做标记
cz(e,f);
printf("%d",k);
return 0;
}
# 马的遍历
## 题目描述
有一个 n *?m?的棋盘，在某个点 (x, y)?上有一个马，要求你计算出马到达棋盘上任意一个点最少要走几步。
## 输入格式
输入只有一行四个整数，分别为 n, m, x, y。
## 输出格式
一个 n *?m的矩阵，代表马到达某个点最少要走几步（不能到达则输出 -1）。
## 样例 #1
### 样例输入 #1
```
3 3 1 1
```
### 样例输出 #1
```
0 ? ?3 ? ?2 ? ?
3 ? ?-1 ? 1 ? ?
2 ? ?1 ? ?4
```
## 提示
### 数据规模与约定
对于全部的测试点，保证 1 <=?x <=?n <=?400，1 <=?y <=?m <=400。
这道题要用到与dfs对应的bfs（广度搜索）。也是bfs的简单运用，数据结构是队列。
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int g[410][410]; //模拟棋盘
int j[410*410][2]; //定义可以保存整个棋盘的队列
int a,b,e,f;
int l=1,r=1; //保存队列出口和入口
int h[9][2]={{-1,-2},{-2,-1},{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2}}; //马可以跳的八个方向
int cz()
{
int tx,ty,n,x;
while(l<=r) //队列走完就停止
{
for(n=0;n<9;n++) //走八个方向
{
tx=j[l][0]+h[n][0];
ty=j[l][1]+h[n][1];
if(tx<1||ty<1||tx>a||ty>b) //不走出棋盘
continue;
if(g[tx][ty]==-1) //这个点没走到过
{
g[tx][ty]=g[j[l][0]][j[l][1]]+1; //到这里要的步数为他的上一个位置的步数加一
j[++r][0]=tx; //添加到队列
j[r][1]=ty;
}
}
l++; //出队列
}
return 0;
}
int main()
{
int x1,x,y1,z,y;
scanf("%d%d%d%d",&a,&b,&e,&f);
for(x=1;x<=a;x++)
for(y=1;y<=b;y++)
{
g[x][y]=-1; //初始化数组为-1
}
g[e][f]=0; //起点步数为0
j[1][0]=e;
j[1][1]=f; //添加起点
cz();
for(x=1;x<=a;x++)
{
for(y=1;y<=b;y++)
{
printf("%-5d",g[x][y]);
}
printf("\n");
}
return 0;
}# 填涂颜色
## 题目描述
由数字 0?组成的方阵中，有一任意形状的由数字 1?构成的闭合圈。现要求把闭合圈内的所有空间都填写成 2。例如：6*6的方阵（n=6），涂色前和涂色后的方阵如下：
如果从某个 0出发，只向上下左右 4?个方向移动且仅经过其他 0?的情况下，无法到达方阵的边界，就认为这个 0?**在闭合圈内**。闭合圈不一定是环形的，可以是任意形状，但保证**闭合圈内**的0?是连通的（两两之间可以相互到达）。
```plain
0 0 0 0 0 0
0 0 0 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 1 0 1
1 1 1 1 1 1
```
```plain
0 0 0 0 0 0
0 0 0 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 1 2 1
1 1 1 1 1 1
```
## 输入格式
每组测试数据第一行一个整数 n(1 <=?n <=?30)。
接下来 n?行，由 0?和 1?组成的 n *?n?的方阵。
方阵内只有一个闭合圈，圈内至少有一个 0。
## 输出格式
已经填好数字 2?的完整方阵。
## 样例 #1
### 样例输入 #1
```
6
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 0 0 1
1 1 1 1 1 1
```
### 样例输出 #1
```
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 2 2 1
1 1 1 1 1 1
```
## 提示
对于 100\%?的数据，1 <=?n <=?30。
用bfs，以四周为起点都走一遍没走到的就是被包围起来的
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int g[40][40];
int g1[40][40];
int j[40*40][2];
int n;
int l=1,r=1;
int h[4][2]={{1,0},{0,1},{0,-1},{-1,0}};
int cz()
{
int tx,ty,m,x;
while(l<=r)
{
for(m=0;m<4;m++)
{
tx=j[l][0]+h[m][0];
ty=j[l][1]+h[m][1];
if(tx<1||ty<1||tx>n||ty>n)
continue;
if(g1[tx][ty]==0)
{
g1[tx][ty]=1;
j[++r][0]=tx;
j[r][1]=ty;
}
}
l++;
}
return 0;
}
int main()
{
int x,y,z;
scanf("%d",&n);
for(x=1;x<=n;x++)
for(y=1;y<=n;y++)
scanf("%d",&g[x][y]);
for(x=1;x<=n;x++)
for(y=1;y<=n;y++)
{
g1[x][y]=g[x][y];
if(g[x][y]==0)
if(x==1||x==n||y==1||y==n)
{
j[r][0]=x;
j[r++][1]=y;
}
}
r--;
cz();
for(x=1;x<=n;x++)
{
for(y=1;y<=n;y++)
if(g1[x][y]==1)
{
printf("%d ",g[x][y]);
}
else
printf("2 ");
printf("\n");
}
return 0;
}# [USACO10OCT] Lake Counting S
## 题面翻译
由于近期的降雨，雨水汇集在农民约翰的田地不同的地方。我们用一个 N*?M(1<=N* N<=?100, 1<=?M<=?100)?的网格图表示。每个网格中有水（`W`） 或是旱地（`.`）。一个网格与其周围的八个网格相连，而一组相连的网格视为一个水坑。约翰想弄清楚他的田地已经形成了多少水坑。给出约翰田地的示意图，确定当中有多少水坑。
输入第 1行：两个空格隔开的整数：N?和 M。
第 2?行到第 N+1?行：每行 M?个字符，每个字符是 `W` 或 `.`，它们表示网格图中的一排。字符之间没有空格。
输出一行，表示水坑的数量。
## 题目描述
Due to recent rains, water has pooled in various places in Farmer John's field, which is represented by a rectangle of N x M (1 <= N <= 100; 1 <= M <= 100) squares. Each square contains either water ('W') or dry land ('.'). Farmer John would like to figure out how many ponds have formed in his field. A pond is a connected set of squares with water in them, where a square is considered adjacent to all eight of its neighbors. Given a diagram of Farmer John's field, determine how many ponds he has.
## 输入格式
Line 1: Two space-separated integers: N and M \* Lines 2..N+1: M characters per line representing one row of Farmer John's field. Each character is either 'W' or '.'. The characters do not have spaces between them.
## 输出格式
Line 1: The number of ponds in Farmer John's field.
## 样例 #1
### 样例输入 #1
```
10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.
```
### 样例输出 #1
```
3
```
## 提示
OUTPUT DETAILS: There are three ponds: one in the upper left, one in the lower left, and one along the right side.
运用dfs，但是将起点改为有‘W'存在的地方，注意'W'为大写。
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
char g[110][110];
int a,b,k;
int h[9][2]={{1,0},{0,1},{0,-1},{-1,0},{-1,-1},{-1,1},{1,1},{1,-1}};
int cz(int x,int y)
{
int tx,ty,m;
for(m=0;m<8;m++)
{
tx=x+h[m][0];
ty=y+h[m][1];
if(tx<1||ty<1||tx>a||ty>b)
continue;
if(g[tx][ty]=='W')
{
g[tx][ty]='.';
cz(tx,ty);
}
}
return 0;
}
int main()
{
int x,y,z;
scanf("%d%d",&a,&b);
for(x=1;x<=a;x++)
{
scanf("%s",g[x]+1);
getchar();
}
for(x=1;x<=a;x++)
{
for(y=1;y<=b;y++)
if(g[x][y]=='W')
{
g[x][y]='.';
cz(x,y);
k++;
}
}
printf("%d",k);
return 0;
}# 自然数的拆分问题
## 题目描述
任何一个大于 1?的自然数 n，总可以拆分成若干个小于 n?的自然数之和。现在给你一个自然数 n，要求你求出 n?的拆分成一些数字的和。每个拆分后的序列中的数字从小到大排序。然后你需要输出这些序列，其中字典序小的序列需要优先输出。
## 输入格式
输入：待拆分的自然数 n。
## 输出格式
输出：若干数的加法式子。
## 样例 #1
### 样例输入 #1
```
7
```
### 样例输出 #1
```
1+1+1+1+1+1+1
1+1+1+1+1+2
1+1+1+1+3
1+1+1+2+2
1+1+1+4
1+1+2+3
1+1+5
1+2+2+2
1+2+4
1+3+3
1+6
2+2+3
2+5
3+4
```
## 提示
数据保证2<=?n<=?8。
全排列的进阶用法，用dfs解决
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int g[11];
int n;
int cz(int l,int r,int step,int sum)
{
int x,y;
for(x=l;x<r;x++)
{
g[step]=x;
if(sum+x>n)
return 0;
if(sum+x==n)
{
for(x=0;x<=step-1;x++)
printf("%d+",g[x]);
printf("%d\n",g[x]);
g[step]=0;
return 0;
}
else
cz(x,r,step+1,sum+x);
g[step]=0;
}
return 0;
}
int main()
{
scanf("%d",&n);
cz(1,n,0,0);
return 0;
}今天对dfs和bfs进行了一些习题的训练能够初步掌握两种搜索方法，可以解决一些浅显的小题。对数据结构有一丝的了解，明白了栈和队列的基本运行形式，可以初步运用到做题中。