题目链接: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; }