9 条题解
-
2
#include <math.h> #include <stdio.h> #include <iostream> #include <string.h> #include <algorithm> #include <queue> using namespace std; char a[155][155]; struct node { int x,y,step; }; int n , m; int dx[] = {1,1,-1,-1,2,2,-2,-2}; int dy[] = {2,-2,2,-2,1,-1,1,-1}; int bfs(int x , int y) { queue<node> p; p.push( (node){x,y,0} ); a[x][y] = '*'; while(!p.empty()) { node t = p.front(); p.pop(); for(int i = 0 ; i < 8 ;i++) { x = dx[i] + t.x; y = dy[i] + t.y; if(x < 0 || y < 0 || x>= n || y >= m || a[x][y]=='*') continue; if(a[x][y] == 'H') return t.step + 1; a[x][y] = '*'; p.push((node){x,y,t.step + 1}); } } return -1; } int main() { cin >> m >> n; int sx,sy; for(int i = 0 ; i < n ; i++) { cin >> a[i]; for(int j = 0 ; j < m ; j++) { if(a[i][j] == 'K') sx = i , sy = j; } } cout << bfs(sx,sy); return 0; } -
1
#include<bits/stdc++.h> using namespace std; int n,m,sx,sy,ex,ey; char ch; int a[155][155]; bool qp[155][155]; struct id { int x,y,s; }; queue<id>q; int xx[8]={1,1,-1,-1,2,2,-2,-2}; int yy[8]={2,-2,2,-2,1,-1,1,-1}; int main() { memset(qp,false,sizeof(qp)); cin>>n>>m; for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) { cin>>ch; if(ch=='*')continue; qp[i][j]=true; if(ch=='K')sx=i,sy=j; if(ch=='H')ex=i,ey=j; } } q.push(id{sx,sy,0}); qp[sx][sy]=false; while(!q.empty()) { id t=q.front(); q.pop(); for(int i=0;i<8;i++) { int nx=t.x+xx[i]; int ny=t.y+yy[i]; if(qp[nx][ny]) { if(nx==ex&&ny==ey) { cout<<t.s+1; return 0; } q.push(id{nx,ny,t.s+1}); qp[nx][ny]=false; } } } } -
0
jinhongxian LV 7 @ 2025-4-19 18:12:01
#include <math.h> #include <stdio.h> #include #include <string.h> #include #include using namespace std; char a[155][155]; struct node { int x,y,step; }; int n , m; int dx[] = {1,1,-1,-1,2,2,-2,-2}; int dy[] = {2,-2,2,-2,1,-1,1,-1}; int bfs(int x , int y) { queue p; p.push( (node){x,y,0} ); a[x][y] = ''; while(!p.empty()) { node t = p.front(); p.pop(); for(int i = 0 ; i < 8 ;i++) { x = dx[i] + t.x; y = dy[i] + t.y; if(x < 0 || y < 0 || x>= n || y >= m || a[x][y]=='') continue; if(a[x][y] == 'H') return t.step + 1; a[x][y] = '*'; p.push((node){x,y,t.step + 1}); } } return -1; } int main() { cin >> m >> n; int sx,sy; for(int i = 0 ; i < n ; i++) { cin >> a[i]; for(int j = 0 ; j < m ; j++) { if(a[i][j] == 'K') sx = i , sy = j; } } cout << bfs(sx,sy); return 0; }
-
0
#include<bits/stdc++.h> using namespace std; int n,m,sx,sy,ex,ey; char ch; int a[155][155]; bool qp[155][155]; struct id { int x,y,s; }; queue<id>q; int xx[8]={1,1,-1,-1,2,2,-2,-2}; int yy[8]={2,-2,2,-2,1,-1,1,-1}; int main() { memset(qp,false,sizeof(qp)); cin>>n>>m; for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) { cin>>ch; if(ch=='*')continue; qp[i][j]=true; if(ch=='K')sx=i,sy=j; if(ch=='H')ex=i,ey=j; } } q.push(id{sx,sy,0}); qp[sx][sy]=false; while(!q.empty()) { id t=q.front(); q.pop(); for(int i=0;i<8;i++) { int nx=t.x+xx[i]; int ny=t.y+yy[i]; if(qp[nx][ny]) { if(nx==ex&&ny==ey) { cout<<t.s+1; return 0; } q.push(id{nx,ny,t.s+1}); qp[nx][ny]=false; } } } } -
0
XZYxuzhiyuan LV 7 @ 2022-4-2 19:59:17
#include<bits/stdc++.h> using namespace std; const int N = 155; int n, m; char str[N][N]; int dis[N][N]; int dir[8][2] = {{1, 2}, {2, 1}, {2, -1,}, {-1, 2}, {-2, 1}, {1, -2}, {-2, -1}, {-1, -2}}; queue<pair<int, int> >q; bool cp(int x, int y) { if(x < 1 || y < 1 || x > n || y > m || str[x][y] == '*' || dis[x][y] != -1) return false; else return true; } int bfs(int ex, int ey) { while(q.size()) { pair<int,int>ad; ad= q.front(); q.pop(); if(ad.first == ex &&ad.second == ey) return dis[ad.first][ad.second]; for(int i = 0; i < 8; i++) { int xx = dir[i][0] +ad.first; int yy = dir[i][1] +ad.second; if(cp(xx, yy)) { dis[xx][yy] = dis[ad.first][ad.second] + 1; q.push(make_pair(xx, yy)); } } } } int main() { int ex, ey; ios::sync_with_stdio(false); memset(dis, -1, sizeof(dis)); cin >> m >> n; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cin>>str[i][j]; if(str[i][j]=='K') { q.push(make_pair(i,j)); dis[i][j]=0; } if(str[i][j]=='H') { ex=i; ey=j; } } } cout<<bfs(ex,ey); return 0; } -
-2
liqinyi001 LV 4 @ 2022-7-31 20:32:31
#include <math.h> #include <stdio.h> #include #include <string.h> #include #include using namespace std; char a[155][155]; struct node { int x,y,step; }; int n , m; int dx[] = {1,1,-1,-1,2,2,-2,-2}; int dy[] = {2,-2,2,-2,1,-1,1,-1}; int bfs(int x , int y) { queue p; p.push( (node){x,y,0} ); a[x][y] = ''; while(!p.empty()) { node t = p.front(); p.pop(); for(int i = 0 ; i < 8 ;i++) { x = dx[i] + t.x; y = dy[i] + t.y; if(x < 0 || y < 0 || x>= n || y >= m || a[x][y]=='') continue; if(a[x][y] == 'H') return t.step + 1; a[x][y] = '*'; p.push((node){x,y,t.step + 1}); } } return -1; } int main() { cin >> m >> n; int sx,sy; for(int i = 0 ; i < n ; i++) { cin >> a[i]; for(int j = 0 ; j < m ; j++) { if(a[i][j] == 'K') sx = i , sy = j; } } cout << bfs(sx,sy); return 0; }
-
-2
#include <bits/stdc++.h> using namespace std; const int MAXN = 1e3 + 10; int n, m, startx, starty, endx, endy, a[MAXN][MAXN], ans = 0; int dir[8][2] = {{-2,-1},{2,1},{-1,2},{1,-2},{-2,1},{2,-1},{1,2},{-1,-2}}; int front = 0,rear = 0; queue<int> qx, qy; void bfs(int x,int y){ qx.push(x); qy.push(y); a[x][y] = 1; while(!qx.empty()){ for(int i = 0;i <= 7; i++){ int tx = qx.front() + dir[i][0]; int ty = qy.front() + dir[i][1]; if(tx == endx && ty == endy){ ans++; return ; } if(tx > n || ty > m || ty <0 || tx < 0 || a[tx][ty] == 1){ continue; } qx.push(tx); qy.push(ty); rear++; a[tx][ty] = 1; } qx.pop(); qy.pop(); if(front == 0 && rear != 0){ front = rear; rear = 0; ans++; } front--; } } int main(){ string line; cin >> m >> n; for(int i = 1;i <= n; i++){ cin >> line; for(int j = 0;j < line.size(); j++){ if(line[j] == '.')a[i][j + 1] = 0; else if(line[j] == '*')a[i][j + 1] = 1; else if(line[j] == 'K'){ a[i][j + 1] = 1; startx = i,starty = j + 1; } else if(line[j] == 'H'){ a[i][j + 1] = 0; endx = i,endy = j + 1; } } } bfs(startx, starty); cout << ans << endl; } -
-2
// #include <math.h> #include <stdio.h> #include #include <string.h> #include #include using namespace std; char a[155][155]; struct node { int x,y,step; }; int n , m; int dx[] = {1,1,-1,-1,2,2,-2,-2}; int dy[] = {2,-2,2,-2,1,-1,1,-1}; int bfs(int x , int y) { queue p; p.push( (node){x,y,0} ); a[x][y] = ''; while(!p.empty()) { node t = p.front(); p.pop(); for(int i = 0 ; i < 8 ;i++) { x = dx[i] + t.x; y = dy[i] + t.y; if(x < 0 || y < 0 || x>= n || y >= m || a[x][y]=='') continue; if(a[x][y] == 'H') return t.step + 1; a[x][y] = ''; p.push((node){x,y,t.step + 1}); } } return -1; } int main() { cin >> m >> n; int sx,sy; for(int i = 0 ; i < n ; i++) { cin >> a[i]; for(int j = 0 ; j < m ; j++) { if(a[i][j] == 'K') sx = i , sy = j; } } cout << bfs(sx,sy); return 0; }
-
-2
#include <math.h> #include <stdio.h> #include #include <string.h> #include #include using namespace std; char a[155][155]; struct node { int x,y,step; }; int n , m; int dx[] = {1,1,-1,-1,2,2,-2,-2}; int dy[] = {2,-2,2,-2,1,-1,1,-1}; int bfs(int x , int y) { queue p; p.push( (node){x,y,0} ); a[x][y] = ''; while(!p.empty()) { node t = p.front(); p.pop(); for(int i = 0 ; i < 8 ;i++) { x = dx[i] + t.x; y = dy[i] + t.y; if(x < 0 || y < 0 || x>= n || y >= m || a[x][y]=='') continue; if(a[x][y] == 'H') return t.step + 1; a[x][y] = '*'; p.push((node){x,y,t.step + 1}); } } return -1; } int main() { cin >> m >> n; int sx,sy; for(int i = 0 ; i < n ; i++) { cin >> a[i]; for(int j = 0 ; j < m ; j++) { if(a[i][j] == 'K') sx = i , sy = j; } } cout << bfs(sx,sy); return 0; }
- 1