东方博宜OJ1586: 【入门】扫地机器人题解

题目传送门
先把机器人放在出发点(1,1)点上,机器人在每个点上都会沿用如下的规则来判断下一个该去的点是哪里。规则:优先向右,如果向右不能走(比如:右侧出了矩形或者右侧扫过了)则尝试向下,向下不能走则尝试向左,向左不能走则尝试向上;直到所有的点都扫过。
可知我们要用dfsdx[4]dy[4]有优先级。
dx[4]dy[4]可以这样设置优先级:

dx[4]={0,1,0,-1};
dy[4]={1,0,-1,0};

数据规模:n<=9,m<=9,数组定义a[11][11]就够了。
其他的就没什么好说的了,上代码吧。

#include<iostream>
#include<iomanip>
using namespace std;
int n,m,cnt=1,a[11][11];//初始化 
int dx[4]={0,1,0,-1};//x偏移量 
int dy[4]={1,0,-1,0};//y偏移量 
void dfs(int x,int y){
	a[x][y]=cnt;//赋值 
	cnt++;//数字+1 
	for(int i=0;i<4;i++){
		int nx,ny;
		nx=x+dx[i];//新的x 
		ny=y+dy[i];//新的y 
		if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&!a[nx][ny]){//没访问过 
			dfs(nx,ny);//dfs 
		}
	}
}
int main(){
	cin>>n>>m;
	dfs(1,1);//从(1,1)开始 
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cout<<setw(3)<<a[i][j];//记得加setw(3) 
		}
		cout<<endl;
	}
	return 0;
} 
上一篇:2021牛客暑期多校训练营1


下一篇:2021-08-05