8 条题解

  • 4
    @ 2021-10-25 17:39:20 
    #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
      @ 2024-12-23 17:17:42 
      #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
        @ 2023-1-6 12:29:35 
        #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
          @ 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
            @ 2022-7-31 20:32:31

            #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; }

            • -2
              @ 2022-2-11 16:38:41 
              #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
                @ 2021-10-25 18:01:17

                // #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; }

                • -2
                  @ 2021-10-25 18:00:33

                  #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

                  象棋中马的走法

                  信息

                  ID
                  99
                  时间
                  1000ms
                  内存
                  128MiB
                  难度
                  5
                  标签
                  递交数
                  363
                  已通过
                  131
                  上传者
                  1. 关于
                  2. 联系我们
                  3. 隐私
                  4. 服务条款
                  5. 版权申诉
                  6. Language
                  7. Theme
                  3. Worker 0 in 19ms
                  4. Powered by Hydro v3.15.13 Community