一、 迷宫
1.题目描述
给定一个 N × M N \times M N×M 方格的迷宫,迷宫里有 T T T 处障碍,障碍处不可通过。
在迷宫中移动有上下左右四种方式,每次只能移动一个方格。数据保证起点上没有障碍。
给定起点坐标和终点坐标,每个方格最多经过一次,问有多少种从起点坐标到终点坐标的方案。
2.输入格式
第一行为三个正整数 N , M , T N,M,T N,M,T,分别表示迷宫的长宽和障碍总数。
第二行为四个正整数 S X , S Y , F X , F Y SX,SY,FX,FY SX,SY,FX,FY, S X , S Y SX,SY SX,SY 代表起点坐标, F X , F Y FX,FY FX,FY 代表终点坐标。
接下来 T T T 行,每行两个正整数,表示障碍点的坐标。
3.输出格式
输出从起点坐标到终点坐标的方案总数。
样例 #1
样例输入 #1
2 2 1
1 1 2 2
1 2
样例输出 #1
1
4.思路
用一个数组记忆障碍所在位置和之前遍历时是否经过,若在一次遍历中结果是能到达终点则sum++。
5.代码
#include<bits/stdc++.h>
using namespace std;
int n,m,t,sx,fx,sy,fy;
int sum;
int a[6][6];
bool vis[6][6];
int xx[5]={-1,0,1,0};
int yy[5]={0,1,0,-1};
void dfs(int x,int y){
int next_x,next_y;
if(x==fx&&y==fy){
sum++;
return ;
}
for(int i=0;i<=3;i++){
next_x=x+xx[i];
next_y=y+yy[i];
if(next_x>=1&&next_x<=n&&next_y>=1&&next_y<=m&&vis[next_x][next_y]==false){
vis[next_x][next_y]=true;
dfs(next_x,next_y);
vis[next_x][next_y]=false;
}
}
}
int main(){
cin>>n>>m>>t;
cin>>sx>>sy>>fx>>fy;
for(int i=1;i<=t;i++){
int x,y;cin>>x>>y;
vis[x][y]=true;
}
vis[sx][sy]=true;
dfs(sx,sy);
cout<<sum;
return 0;
}
二、马的遍历
1.题目描述
有一个 n × m n \times m n×m 的棋盘,在某个点 ( x , y ) (x, y) (x,y) 上有一个马,要求你计算出马到达棋盘上任意一个点最少要走几步。
2.输入格式
输入只有一行四个整数,分别为 n , m , x , y n, m, x, y n,m,x,y。
3.输出格式
一个 n × m n \times m n×m 的矩阵,代表马到达某个点最少要走几步(不能到达则输出 − 1 -1 −1)。文章来源:https://www.toymoban.com/news/detail-412816.html
样例 #1
样例输入 #1
3 3 1 1
样例输出 #1
0 3 2
3 -1 1
2 1 4
4.思路
将每次马能走到的八个位置求出,再进行判断能不能到达,经过的地点用数组记忆下次不再经过。若遍历一趟后没过某一点,此点变为一(直接一开始全部将数组初始化为-1).文章来源地址https://www.toymoban.com/news/detail-412816.html
5.代码
#include<bits/stdc++.h>
using namespace std;
int n,m,hx,hy,sum=0;
queue<pair<int ,int> >q;
int a[500][500];
bool vis[500][500];
int xx[8]={-2,-2,2,2,-1,-1,1,1};
int yy[8]={-1,1,-1,1,-2,2,-2,2};
int main(){
cin>>n>>m>>hx>>hy;int sum=5;
memset(a,-1,sizeof(a));
vis[hx][hy]=1;a[hx][hy]=0;
q.push(make_pair(hx,hy));
while(!q.empty()){
int x=q.front().first;
int y=q.front().second;
q.pop();
for(int i=0;i<=7;i++){
int x2=x+xx[i];
int y2=y+yy[i];
if(x2>=1&&x2<=n&&y2>=1&&y2<=m&&vis[x2][y2]==false){
vis[x2][y2]=true;
q.push(make_pair(x2,y2));
a[x2][y2]=a[x][y]+1;
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cout<<a[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
到了这里,关于week4 搜索的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!