[AcWing] 第 13 场周赛

前言

传送门 :

B.机器人走迷宫

t a g : tag: tag: 简单好题 bfs&&dfs 模拟

题意 :
给定一个含有路障和单个终点和起点的网格,给定一个 0123 0123 0123的字符串,表示机器人的运动方式,让你给 0 , 1 , 2 , 3 0,1,2,3 0,1,2,3标定方向,询问有多少种方式可以从起点走到终点

思路 :
显然,这题就是先 d f s dfs dfs排列出所有的方式,然后再用 b f s bfs bfs判断(虽然我用的不是

但是怎么处理方向问题呢 ? ? ?

我们考虑使用两个 m a p map map,第一个用来映射方向,第二个用来映射字符串

即 D [ i ] = p [ i ] 当 前 的 排 列 中 ′ i ′ 表 示 ′ p [ i ] ′ D[i]=p[i] 当前的排列中'i'表示'p[i]' D[i]=p[i]当前的排列中′i′表示′p[i]′
m p [ i ] = { 0 , − 1 } 表 示 ′ i ′ 的 方 向 是 向 下 mp[i]=\{0,-1\} 表示'i'的方向是向下 mp[i]={0,−1}表示′i′的方向是向下

然后判断即可

code :

map mp;
map D;
const int N = 60,M = 60;

int ans;
int p[5],st[5];
int n,m;
char g[N][M];
string s;
int sx,sy;
int ex,ey;

void init(){
	mp[0]={0,1};
	mp[1]={1,0};
	mp[2]={0,-1};
	mp[3]={-1,0};
}

bool bfs(){
	int tx = sx;
	int ty = sy;
	
	
	
	for(auto _s : s){
		
		tx +=mp[D[_s-'0']].x;
		ty +=mp[D[_s-'0']].y;
	
		if(g[tx][ty] == '#')return false;
		if(tx > n || txm || ty>m;
	ans = 0 ;
	
	for(int i=1;ig[i][j];
			if(g[i][j] == 'S') sx = i ,sy = j;
			if(g[i][j] == 'E') ex = i ,ey = j;
	}
	
	cin>>s;//cin>>s;
	dfs(0);
	coutm;
	cin>>(w+1);
	for(int i=1;i>a>>b;
		
		g[a].pb(b);
		in[b]++;
	}
	
	if(!topsort()) cout