宇宙无敌超级大蒟蒻求解答
  • 板块P1443 马的遍历
  • 楼主_O__o_
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/5/26 14:58
  • 上次更新2023/10/23 14:44:39
查看原帖
宇宙无敌超级大蒟蒻求解答
741120
_O__o_楼主2023/5/26 14:58
/***********************************
            .-'''''-.
          .'         `.
         :             :
        :               :
        :      _/|      :
         :   =/'/      :
          `._/ |     .'
       (   /  ,|...-'
        \_/^\/||__
     _/~  `""~`"` \_
  __/  -'/  `-._ `\	_\__
/     /-'`  `\   \  \-.\
*************************************/

#include<bits/stdc++.h>

using namespace std;
struct state{
	int x,y,step;
}q[100001];
int head = 0,tail = 0;
int n,m;
int sx,sy;
int bs = 1;
int map_[101][101];
bool vis[101][101];
int dir[8][2] = {
	-1,-2,
	-1,+2,
	+1,-2,
	+1,+2,
	-2,-1,
	-2,+1,
	+2,-1,
	+2,+1
};
void bfs(){
	q[tail] = (state){sx,sy,0};
	vis[sx][sy] = 1;
	tail++;
	state now;
	while(head < tail){
		now = q[head];
		if(bs == n * m){
			for(int i = 1;i <= n;i++){
				for(int j = 1;j <= m;j++){
					if(map_[i][j] == 999){
						cout << 0 << "    ";
						continue;
					}
					if(map_[i][j] > 0){
						cout << map_[i][j] << "    ";
						continue;
					}
					
					cout << -1 << "    ";
				}
				cout << endl;	
			}
				
		}
	
		for(int i = 0;i < 8;i++){
			int xx = now.x + dir[i][0],
				yy = now.y + dir[i][1],
				sstep = now.step + 1;
			if(xx >= 1 && xx <= n && yy >= 1 && yy <= m && !vis[xx][yy]){
				map_[xx][yy] = head;
				q[tail++] = (state){xx,yy,sstep};
				bs++;
			}	
		}
		
	head++;
	now.step++;
	}
	
}
int main() {
	//step 1. 读题、声明变量

	//step 2. 输入
	cin >> n >> m;
	cin >> sx >> sy;
	//step 3. 处理
	map_[sx][sy] = 999;
	//step 4. 输出
	bfs();
	return 0;
}


2023/5/26 14:58
加载中...