1 条题解

  • 1
    @ 2023-11-19 16:53:03
    /*****************************************
    Note:
    ******************************************/
    #include <queue>
    #include <math.h>
    #include <stack>
    #include <stdio.h>
    #include <iostream>
    #include <vector>
    #include <iomanip>
    #include <string.h>
    #include <algorithm>
    using namespace std;
    #define LL long long
    const int N = 1e6 + 10;
    const int INF = 0x3f3f3f3f;
    int n , m;
    char a[205][205];
    struct node
    {
    	int x, y,step;
    };
    int dx[] = {1,1,-1,-1,2,2,-2,-2};
    int dy[] = {2,-2,2,-2,1,-1,1,-1};
    int bfs(int sx , int sy)
    {
    	queue<node> p;
    	p.push((node){sx,sy,0});
    	a[sx][sy] = '*';
    	while(!p.empty())
    	{
    		node t = p.front();
    		p.pop();
    		for(int i = 0 ; i < 8 ; i++)
    		{
    			int x = t.x + dx[i];
    			int y = t.y + dy[i];
    			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;
    	for(int i = 0 ; i < n ; i++)
    		cin >> a[i];
    	int sx,sy;
    	sx = sy = -1;
    
    	for(int i = 0 ; i < n && sx == -1 ; i++)
    		for(int j = 0 ; j < m && sx == -1; j++)
    			if(a[i][j] == 'K')
    				sx = i , sy = j;
    
    	cout << bfs(sx,sy);
    	return 0;
    }
    
    • 1

    信息

    ID
    2568
    时间
    1000ms
    内存
    256MiB
    难度
    7
    标签
    递交数
    202
    已通过
    53
    上传者