刘顺松.zip

//先采用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; }