1 solutions

  • 1
    @ 2023-3-25 22:07:43
    #include <iostream>
    #include <queue>
    const int N = 155;
    using namespace std;
    int n, m;
    bool vis[N][N];
    char mp[N][N];
    
    int dx[8] = {-2, -1, -2, -1, 1, 2, 2, 1}, dy[8] = {-1, -2, 1, 2, -2, -1, 1, 2};
    struct Edge {
    	int x, y, w;
    };
    queue<Edge> que;
    bool check(int x, int y) {
    	if (x > 0 && y > 0 && x <= m && y <= n && !vis[x][y] && mp[x][y] != '*')
    		return true;
    	return false;
    }
    int bfs() {
    	while (!que.empty()) {
    		Edge p = que.front();
    		que.pop();
    		if (mp[p.x][p.y] == 'H') {
    			return p.w;
    		}
    		if (vis[p.x][p.y])
    			continue;
    		vis[p.x][p.y] = 1;
    		for (int i = 0; i < 8; i++) {
    			int nx = p.x + dx[i], ny = p.y + dy[i];
    			if (check(nx, ny)) {
    				que.push({nx, ny, p.w + 1});
    			}
    		}
    	}
    	return -1;
    }
    int main() {
    	scanf("%d %d", &n, &m);
    	for (int i = 1; i <= m; i++) {
    		for (int j = 1; j <= n; j++) {
    			cin >> mp[i][j];
    			if (mp[i][j] == 'K') {
    				que.push({i, j, 0});
    			}
    		}
    	}
    	printf("%d", bfs());
    	return 0;
    }
    

    Information

    ID
    778
    Time
    1000ms
    Memory
    128MiB
    Difficulty
    6
    Tags
    # Submissions
    47
    Accepted
    14
    Uploaded By