6 solutions
-
1
bfs
#include <bits/stdc++.h>//bfs版 using namespace std; bool vis[105][105]; int dx[12] = {1, 2, -1, 2, 1, -2, -1, -2, 2, -2, 2, -2}; int dy[12] = {2, 1, 2, -1, -2, 1, -2, -1, 2, 2, -2, -2}; int ax, ay, bx, by; struct node { int xx; int yy; int s; }; // 广搜 int bfs(int x, int y) { //cout << x << " " << y << endl; for (int i = 1; i <= 100; i++)//初始化 { for (int j = 1; j <= 100; j++) { vis[i][j] = false; } } vis[x][y] = true;//当前位置 queue<node> q; q.push({x, y, 0}); while (!q.empty()) { int cx = q.front().xx; int cy = q.front().yy; int steps = q.front().s; q.pop();//用完了就扔掉 //cout << cx << " " << cy << " " << steps << endl; if (cx == 1 && cy == 1) { return steps; } for (int i = 0; i < 12; i++) { int nx = cx + dx[i]; int ny = cy + dy[i]; if (nx >= 1 && nx <= 100 && ny >= 1 && ny <= 100 &&!vis[nx][ny])//无越界没走过 { q.push({nx, ny, steps + 1}); vis[nx][ny] = true; } } } } int main() { cin >> ax >> ay >> bx >> by; int steps1 = bfs(ax, ay); int steps2 = bfs(bx, by); cout << steps1 << endl << steps2; return 0; }-
C24zhengshunyuan @ 2025-2-26 13:56:23
dfs过不了会超时
#include <bits/stdc++.h>//dfs版 using namespace std; int ans = 1000005; bool vis[105][105]; int dx[12] = {-2, -2, -1, -1, 1, 1, 2, 2, -2, -2, 2, 2}; int dy[12] = {-1, 1, -2, 2, -2, 2, -1, 1, -2, 2, -2, 2}; void dfs(int x, int y, int s) { if (x == 1 && y == 1) { ans = min(ans, s); return; } vis[x][y] = true; for (int i = 0; i < 12; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (vis[nx][ny]==false&&nx>=1&&nx<=100&&ny>=1&&ny<=100) { dfs(nx, ny, s + 1); } } vis[x][y] = false; } int main() { int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; dfs(x1, y1, 0); cout << ans << endl; ans = 1000005; dfs(x2, y2, 0); cout << ans << endl; return 0; }
-
-
1
C23panweiming
LV 8
@ 2024-10-18 13:40:23
bfs的运用
#include<iostream> #include<queue> #include<cstring> using namespace std; int ax,ay,bx,by; int xl[12]={2,1,-2,-1,2,1,-2,-1,2,2,-2,-2}; int yl[12]={1,2,-1,-2,-1,-2,1,2,2,-2,2,-2}; struct xyw { int x,y,w; }; int vis[105][105]; void bfs(int xz,int yz) { memset(vis,0,sizeof vis); queue<xyw>q; q.push({xz,yz}); while(!q.empty()) { int x=q.front().x; int y=q.front().y; int w=q.front().w; q.pop(); if(vis[x][y]) continue; vis[x][y]=1; if(x==1 && y==1) { cout<<w<<"\n"; #warning 复制代码要点好评 break; } for(int i=0;i<12;i++) { int xs=x+xl[i]; int ys=y+yl[i]; if(xs>0 && xs<=100 && ys>0 && ys<=100 && !vis[xs][ys]) q.push({xs,ys,w+1}); } } } int main() { cin>>ax>>ay>>bx>>by; bfs(ax,ay); bfs(bx,by); return 0; } -
0
C24wanghongming
LV 8
@ 2025-2-27 14:04:34
#include <bits/stdc++.h> using namespace std; bool pp[105][105]; int ppx[12]={1,2,-1,2,1,-2,-1,-2,2,-2,2,-2},ppy[12]={2,1,2,-1,-2,1,-2,-1,2,2,-2,-2},px,py; struct node{ int x,y,s; }pnode; int bfs(int x, int y){ for(int i=1;i<=100;i++)for(int j=1;j<=100;j++)pp[i][j]=false; pp[x][y]=true; queue<node>ppp; ppp.push({x, y, 0}); while(!ppp.empty()){ pnode=ppp.front(); ppp.pop(); if(pnode.x==1&&pnode.y== 1)return pnode.s; for(int i=0;i<12;i++){ int px=pnode.x+ppx[i],py=pnode.y+ppy[i]; if(px>=1&&px<=100&&py>=1&&py<=100&&!pp[px][py]){ ppp.push({px,py,pnode.s+1}); pp[px][py]=true; } } } } int main(){ cin>>px>>py; cout<<bfs(px,py)<<endl; cin>>px>>py; cout<<bfs(px,py); return 0; } -
0
C23lvzekai
LV 6
@ 2024-3-20 13:58:26
BFS
#include<bits/stdc++.h> using namespace std; struct s{ int x,y,ans; }; queue<s> q; int fx[20]={2,1,-2,-1,2,1,-2,-1,2,2,-2,-2}; int fy[20]={1,2,-1,-2,-1,-2,1,2,2,-2,2,-2}; bool arr[110][110]; int main(){ int ax,ay,bx,by; cin>>ax>>ay>>bx>>by; q.push({ax,ay,0}); while(q.size()){ int x=q.front().x,y=q.front().y,ans=q.front().ans; //cout<<x<<' '<<y<<'\n'; if(x==1 && y==1){ //if(ax&1 && ay&1) ans++; cout<<ans<<endl; break; } for(int i=0;i<12;i++){ int tx=x+fx[i],ty=y+fy[i]; if(tx<=100 && tx>0 && ty<=100 && ty>0 && !arr[tx][ty]){ arr[tx][ty]=1; q.push({tx,ty,ans+1}); } } q.pop(); } queue<s> q1; q=q1; memset(arr,0,sizeof(arr)); q.push({bx,by,0}); while(q.size()){ int x=q.front().x,y=q.front().y,ans=q.front().ans; //cout<<x<<' '<<y<<'\n'; if(x==1 && y==1){ //if(bx&1 && by&1) ans++; cout<<ans; break; } for(int i=0;i<12;i++){ int tx=x+fx[i],ty=y+fy[i]; if(tx<=100 && tx>0 && ty<=100 && ty>0 && !arr[tx][ty]){ arr[tx][ty]=1; q.push({tx,ty,ans+1}); } } q.pop(); } return 0; }-
C23panweiming
@ 2024-10-18 13:52:34
没注释，差评!!!
-
-
0
C23linboming LV 6 @ 2024-1-26 9:58:33
AC呆马：
#include<bits/stdc++.h> using namespace std; int dx[12]={-2,-2,-1,1,2,2,2,2,1,-1,-2,-2}; int dy[12]={-1,-2,-2,-2,-2,-1,1,2,2,2,2,1}; int main() { int s[101][101],que[10000][4]={0},x1,x2,y1,y2; memset(s,0xff,sizeof(s)); int head=1,tail=1; que[1][1]=1;que[1][2]=1;que[1][3]=0; cin>>x1>>y1>>x2>>y2; while(head<=tail) { for(int d=0;d<=11;d++) { int x=que[head][1]+dx[d]; int y=que[head][2]+dy[d]; if(x>0 && y>0) if(s[x][y]==-1) { s[x][y]=que[head][3]+1; tail++; que[tail][1]=x; que[tail][2]=y; que[tail][3]=s[x][y]; if(s[x1][y1]>0&&s[x2][y2]>0) { cout<<s[x1][y1]<<endl; cout<<s[x2][y2]<<endl; system("pause"); return 0; } } } head++; } return 0; } -
0
C23weizechen
LV 4
@ 2024-1-26 9:57:28
AC歹马（From 一本通）
#include<bits/stdc++.h> using namespace std; int dx[12]={-2,-2,-1,1,2,2,2,2,1,-1,-2,-2}; int dy[12]={-1,-2,-2,-2,-2,-1,1,2,2,2,2,1}; int main() { int s[101][101],que[10000][4]={0},x1,x2,y1,y2; memset(s,0xff,sizeof(s)); int head=1,tail=1; que[1][1]=1;que[1][2]=1;que[1][3]=0; cin>>x1>>y1>>x2>>y2; while(head<=tail) { for(int d=0;d<=11;d++) { int x=que[head][1]+dx[d]; int y=que[head][2]+dy[d]; if(x>0 && y>0) if(s[x][y]==-1) { s[x][y]=que[head][3]+1; tail++; que[tail][1]=x; que[tail][2]=y; que[tail][3]=s[x][y]; if(s[x1][y1]>0&&s[x2][y2]>0) { cout<<s[x1][y1]<<endl; cout<<s[x2][y2]<<endl; system("pause"); return 0; } } } head++; } return 0; }
C24zhengshunyuan
LV 6
@ 2025-2-26 13:53:45
- 1