潘葛宇
( 不干人事的胖鳄鱼)
1
5. 好马不吃回头草
XJOI - 题目ID：15621选做题60分
最新提交：
Wrong Answer
50 分
历史最高：
Wrong Answer
50 分
时间限制: 1000ms
空间限制: 524288kB
题目描述
“好马不吃回头草！”。有道理！！！，虽然鱼大大也不知道道理在哪里，但是他就是觉得这句话很有道理。于是乎，他便养成了一个习惯，下象棋时，他的马从来都是毫无撤退可言！
现给出一张巨大的棋盘，问象棋中的马（走日字型）由鱼大大操控，从棋盘上一个点吃掉另一个点的“帅”最少需要几步。（起点记作0步，帅不动）
注： 鱼大大在黑色方，即上方
【输入格式】
第一行输入一个整数n,表示棋盘的大小为n*n,棋盘两个维度的坐标都是从1到n
接下来两行每行两个整数分别表示马出发点的坐标与帅终点的坐标。（第一个为行，第二个为列）
【输出格式】
输出一个整数，表示最小步数，若无法到达输出-1
【样例输入】
50
1 1
30 50
【样例输出】
26
【数据范围】
3 ≤ n ≤ 500；
哪位大佬能看看我这个50分代码
#include<bits/stdc++.h>
using namespace std;
int n,stX,stY,enX,enY;
int dx[8]={-1,-2,-2,-1,1,2,2,1};
int dy[8]={-2,-1,1,2,-2,-1,1,2};
int vis[305][305];
struct Node{
int x,y,cnt;
};
void bfs(int X,int Y){
queue<Node>qu;
qu.push({X,Y,0});
vis[X][Y]=1;
while (!qu.empty()){
Node now=qu.front();
qu.pop();
if(now.x==enX&&now.y==enY){
if(now.cnt==0)coit<<-1;
else cout<<now.cnt;
return;
}
for(int i=0;i<8;i++){
int nx=now.x+dx[i];
int ny=now.y+dy[i];
int count=now.cnt+1;
if(nx<0 || ny<0 || nx>=n || ny>=n || vis[nx][ny]==1)continue;
qu.push({nx,ny,count});
vis[nx][ny]=1;
}
}
}
int main(){
cin>>n>>stX>>stY>>enX>>enY;
bfs(stX,stY);
return 0;
}
3 个赞
周子寓
(zzy10124)
3
#include<bits/stdc++.h>
using namespace std;
struct node{
int x,y,step;
};
int dx[8]={2,2,-2,-2,1,1,-1,-1};
int dy[8]={1,-1,1,-1,2,-2,2,-2};
queue<node> q;
int a,b,n,c,d,vis[405][405];
char maze[405][405];
void dfs(){
q.push( node{a,b,0}); //起点入队
vis[a][b]=1; //标记起点
maze[a][b]=0;
while(q.size()!=0){ //循环队列
for(int i=0;i<8;i++){ //枚举方向
int tx=q.front().x+dx[i]; //领地计数
int ty=q.front().y+dy[i];
if(tx>=1&&tx<=n&&ty>=1&&ty<=n&&vis[tx][ty]==0){
if(tx==c&&ty==d){
cout<<q.front().step+1;
return ;
}
q.push( node{tx,ty,q.front().step+1} ); //入队
vis[tx][ty]=1;
}
}
q.pop();
}
}
int main(){
cin>>n;
cin>>a>>b;
cin>>c>>d;
dfs();
}
3 个赞
周子寓
(zzy10124)
4
#include<bits/stdc++.h>
using namespace std;
struct node{
int x,y,step;
};
int dx[8]={2,2,-2,-2,1,1,-1,-1};
int dy[8]={1,-1,1,-1,2,-2,2,-2};
queue<node> q;
int a,b,n,c,d,vis[505][505];
void dfs(){
q.push( node{a,b,0}); //起点入队
vis[a][b]=1; //标记起点
while(q.size()!=0){ //循环队列
for(int i=0;i<8;i++){ //枚举方向
int tx=q.front().x+dx[i]; //领地计数
int ty=q.front().y+dy[i];
if(tx>=1&&tx<=n&&ty>=1&&ty<=n&&vis[tx][ty]==0){
if(tx==c&&ty==d){
cout<<q.front().step+1;
return ;
}
q.push( node{tx,ty,q.front().step+1} ); //入队
vis[tx][ty]=1;
}
}
q.pop();
}
}
int main(){
cin>>n;
cin>>a>>b;
cin>>c>>d;
dfs();
}
3 个赞
周子寓
(zzy10124)
9
#include<bits/stdc++.h>
using namespace std;
struct node{
int x,y,step;
};
int dx[8]={2,2,-2,-2,1,1,-1,-1};
int dy[8]={1,-1,1,-1,2,-2,2,-2};
queue<node> q;
int a,b,n,c,d,vis[505][505];
void dfs(){
q.push( node{a,b,0}); //起点入队
vis[a][b]=1; //标记起点
while(q.size()!=0){ //循环队列
for(int i=0;i<8;i++){ //枚举方向
int tx=q.front().x+dx[i]; //领地计数
int ty=q.front().y+dy[i];
if(tx>=1&&tx<=n&&ty>=1&&ty<=n&&vis[tx][ty]==0){
if(tx==c&&ty==d){
cout<<q.front().step+1;
return ;
}
q.push( node{tx,ty,q.front().step+1} ); //入队
vis[tx][ty]=1;
}
}
q.pop();
}
cout<<-1<<endl;
}
int main(){
cin>>n;
cin>>a>>b;
cin>>c>>d;
dfs();
}
2 个赞
陈晟亦
(弈剑のㄨ听雨阁)
11
#include<bits/stdc++.h>
using namespace std;
int vis[505][505];
struct node {
int x, y, step;
};
int dx[4] = {1,2,2,1};
int dy[4] = {-2,-1,1,2};
int n, sx, sy, ex, ey;
void bfs(int x, int y) {
queue <node> q;
q.push(node{x, y, 0});
vis[x][y] = 1;
while (!q.empty()) {
node now = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int xx = now.x + dx[i];
int yy = now.y + dy[i];
if (xx >= 1 && xx <= n && yy >= 1 && yy <= n && vis[xx][yy] == 0) {
vis[xx][yy] = 1;
q.push(node{xx, yy, now.step + 1});
if (xx == ex && yy == ey) {
cout << now.step + 1;
return;
}
}
}
}
cout<<-1;
}
int main() {
cin >> n >> sx >> sy >> ex >> ey;
bfs(sx, sy);
return 0;
}
3 个赞
