//先采用dfs写思路,但会超时//
//BFS专门用于解决求两点之间最短路的问题
//而DFS是用来解决求一个点到另一个点路径总数的问题
/*
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
const int N = 500;
int arr[N][N] = {0};
bool view[N][N];
int dx[8]={-2,-2,-1,-1,2,2,1,1};
int dy[8]={1,-1,2,-2,1,-1,2,-2};//坐标增量
int n,m,x,y;
void dfs(int x,int y,int ans)
{
view[x][y] = true;//标记起始点//
for(int i = 0;i<8;i++)
{
int ret = x + dx[i],res = y + dy[i];
if(ret>=1&&ret<=n&&res>=1&&res<=m)//限制数组范围,避免越界//
{
if(!view[ret][res])//标记以走过的点//
{
arr[ret][res] = ans;
view[ret][res] = true;
dfs(ret,res,ans+1);
}
else if(ans+1<arr[ret][res])//剪枝 //
{
arr[ret][res] = ans;
view[ret][res] = true;
dfs(ret,res,ans+1);
}
}
}
}
int main()
{
cin>>n>>m>>x>>y;
arr[x][y] = 0;
dfs(x,y,1);
for(int i=1;i<=n;i++)
{
for(int j = 1;j<=m;j++)
{
cout<<arr[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
*/ /
//BFs//////////////////////////////////////
#include<iostream>
#include<bits/stdc++.h>
#include<queue>
using namespace std;
const int N = 500;
int arr[N][N];
bool view[N][N];
int n,m,x,y;
int dx[8]={-2,-2,-1,-1,2,2,1,1};
int dy[8]={1,-1,2,-2,1,-1,2,-2};//坐标增量//
struct res
{
int x;
int y;
};
queue<res>r;//申请队列,队列元素类型为res,队列名称为r//
int main()
{
memset(arr,-1,sizeof(arr));
cin>>n>>m>>x>>y;
res start;
start.x = x;
start.y = y;
int text = 0;
r.push(start);//起点入队//
arr[start.x][start.y] = 0;
view[start.x][start.y] = true;//标记起点//
while(!r.empty())//判空//
{
for(int i = 0;i<8;i++)
{
int tx = r.front().x + dx[i];
int ty = r.front().y + dy[i];
if(tx>=1&&tx<=n&&ty>=1&&ty<=m)
{
if(!view[tx][ty])
{
arr[tx][ty] = arr[r.front().x][ r.front().y]+1;
view[tx][ty] = true;
res end;
end.x = tx;
end.y = ty;
r.push(end);//插入队尾//
}
}
}
r.pop();//拓展完移除队首元素,否则陷入是循环//
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cout<<arr[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
没有合适的资源?快使用搜索试试~ 我知道了~
资源推荐
资源详情
资源评论
收起资源包目录
刘顺松.zip (3个子文件)
刘顺松
爱愁.cpp 1KB
ma wenti.cpp 2KB
水坑.cpp 774B
共 3 条
- 1
资源评论
林志呀
- 粉丝: 0
- 资源: 1
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功