ZOJ3865 – Superbot(bfs)

题目链接:ZOJ3865

【题意】走迷宫,’@’为起点,’$’为终点,有一个操作盘,还有选框,每隔P秒,所有方向键都右移一格,有三种选择:

1.向左或者向右移动一格光标。

2.按下当前选中按钮,人往当前按钮的方向走一个。

3.原地等待,不做任何操作。

3种都耗时1秒。求最少几秒到达终点。

【分析】一看就是BFS,表示下状态dp[x][y][i][j]:表示人在(x,y),当前选框落在第i格,在原来基础上所有按键偏移了j格时的用时。

比赛的时候为了保险还加了优先队列,其实只要普通队列就可以了。

【AC CODE】0ms

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <map>
//#include <unordered_map>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 10+5, f[4][2]={{0,-1},{0,1},{-1,0},{1,0}};
const int mv[4][4] = {{0,1,2,3},{3,0,1,2},{2,3,0,1},{1,2,3,0}};
char mp[MAXN][MAXN];
struct NODE{
	int x,y,p,w,cost;
};
int n,m,k;
int ei,ej,dis[MAXN][MAXN][4][4];

int bfs(int si, int sj)
{
	queue<NODE> q;
	clc(dis,-1);
	dis[si][sj][0][0] = 0;
	q.push({si,sj,0,0,0});
	while(!q.empty())
	{
		NODE now = q.front();q.pop();
		if(now.x == ei && now.y == ej) return now.cost;
		//移动光标
		int c = ((now.cost+1)/k)%4;
		NODE to = {now.x,now.y,(now.p+1)%4,c,now.cost+1};
		if(-1 == dis[to.x][to.y][to.p][c])
		{
			dis[to.x][to.y][to.p][c] = now.cost+1;
			q.push(to);
		}
		to = {now.x,now.y,(now.p-1+4)%4,c,now.cost+1};
		if(-1 == dis[to.x][to.y][to.p][c])
		{
			dis[to.x][to.y][to.p][c] = now.cost+1;
			q.push(to);
		}
		//按下按钮
		int ni = now.x+f[mv[now.w][now.p]][0], nj = now.y+f[mv[now.w][now.p]][1];
		if(0 <= ni && n > ni && 0 <= nj && m > nj && '*' != mp[ni][nj])
		{
			to = {ni,nj,now.p,c,now.cost+1};
			if(-1 == dis[to.x][to.y][to.p][c])
			{
				dis[to.x][to.y][to.p][c] = now.cost+1;
				q.push(to);
			}
		}
		to = {now.x,now.y,now.p,c,now.cost+1};
		if(-1 == dis[to.x][to.y][to.p][c])
		{
			dis[to.x][to.y][to.p][c] = now.cost+1;
			q.push(to);
		}
	}
	return -1;
}
int main()
{
#ifdef SHY
	freopen("d:\\1.txt", "r", stdin);
#endif
	int t;
	scanf("%d%*c", &t);
	while(t--)
	{
		scanf("%d %d %d%*c", &n, &m, &k);
		int si,sj;
		rep(i,0,n)
		{
			scanf("%s%*c",mp[i]);
			rep(j,0,m)
			{
				if('@' == mp[i][j])
					si = i, sj = j;
				if('$' == mp[i][j])
					ei = i, ej = j;
			}
		}
		int ans = bfs(si,sj);
		if(-1 == ans) puts("YouBadbad");
		else printf("%d\n", ans);
	}
	return 0;
}

 

发表评论

邮箱地址不会被公开。 必填项已用*标注

请输入正确的验证码