这题思路很简单,也是bfs通常的思路。即在每一轮枚举所有可能出现的情况,将其入队,然后弹出队首。当队列为空时结束搜索。
有以下几点体会:
1.入队的条件尽量多。不然容易死循环,一开始没有加上bfs[a.x][a.y]==-1这个条件,导致已经被搜索到的点重复入队陷入死循环;
2.第一次走到的点标记为1,代表走到这里至少需要一布,然后加上走到上一个点的步数p。其实这里有点dp的意思;
3.这题原点是(1.1),二维题目原点都非常重要,别问我怎么知道的(笑)。
以下是ac代码:
#include<bits/stdc++.h> using namespace std; #define endl '\n' const int N=1e6+9; using ll=long long; struct d{ int x,y; }; int dx[8]={1,1,-1,-1,2,2,-2,-2}; int dy[8]={2,-2,2,-2,1,-1,1,-1}; void solve(){ d d1; int n,m;cin>>n>>m>>d1.x>>d1.y; vector<vector<int>> bfs(n+9,vector<int>(m+9,-1)); bfs[d1.x][d1.y]=0; queue<d> q; q.push(d1); while(!q.empty()){ d a=q.front();q.pop(); d b=a; for(int i=0;i<8;++i){ a.x=b.x,a.y=b.y; a.x+=dx[i],a.y+=dy[i]; if(a.x>=1&&a.y>=1&&a.x<=n&&a.y<=m&&bfs[a.x][a.y]==-1){ q.push(a); bfs[a.x][a.y]=1; bfs[a.x][a.y]+=bfs[a.x-dx[i]][a.y-dy[i]]; } } } for(int i=1;i<=n;++i){ for(int j=1;j<=m;++j){ printf("%-5d",bfs[i][j]); } cout<<endl; } } int main(){ //ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int _=1; //cin>>_; while(_--)solve(); return 0; }