ZOJ Problem Set

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5477

大牛博客：http://www.cnblogs.com/kylehz/p/4420009.html

只不过状态用vis[20][20][4]来记录，每个点都有四个状态，访问过就不能访问

通过控制面板控制机器人找钻石，控制面板每p时间右移一次（队尾变队首），求最短路径

控制面板为左右上下的顺序,初始时光标在左

有3种操作，占用一个单位时间

1. 光标左移（最左的移到最右）或者右移（最右的移到最左）

2.按按钮，机器人会根据光标所指的方向移动一个单位

3.停在原地

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cmath>
  4 #include <vector>
  5 #include <cstring>
  6 #include <string>
  7 #include <algorithm>
  8 #include <string>
  9 #include <set>
 10 #include <functional>
 11 #include <numeric>
 12 #include <sstream>
 13 #include <stack>
 14 #include <map>
 15 #include <queue>
 16 #pragma comment(linker, "/STACK:102400000,102400000")
 17 #define CL(arr, val)    memset(arr, val, sizeof(arr))
 18 
 19 #define ll long long
 20 #define inf 0x7f7f7f7f
 21 #define lc l,m,rt<<1
 22 #define rc m + 1,r,rt<<1|1
 23 #define pi acos(-1.0)
 24 
 25 #define L(x)    (x) << 1
 26 #define R(x)    (x) << 1 | 1
 27 #define MID(l, r)   (l + r) >> 1
 28 #define Min(x, y)   (x) < (y) ? (x) : (y)
 29 #define Max(x, y)   (x) < (y) ? (y) : (x)
 30 #define E(x)        (1 << (x))
 31 #define iabs(x)     (x) < 0 ? -(x) : (x)
 32 #define OUT(x)  printf("%I64d
", x)
 33 #define lowbit(x)   (x)&(-x)
 34 #define Read()  freopen("a.txt", "r", stdin)
 35 #define Write() freopen("b.txt", "w", stdout);
 36 #define maxn 1000000000
 37 #define N 500010
 38 using namespace std;
 39 
 40 int n,m,p;
 41 char mp[20][20];
 42 bool vis[20][20][4];
 43 int dx[4]={0,0,-1,1};
 44 int dy[4]={-1,1,0,0};
 45 struct point
 46 {
 47     int x,y,step,dir;
 48 }ss;
 49 
 50 point s,e;
 51 
 52 void bfs()
 53 {
 54     queue<point>q;
 55     s.step=s.dir=0;
 56     q.push(s);
 57     while(q.size())
 58     {
 59         point t=q.front();
 60         q.pop();
 61         if(t.x==e.x&&t.y==e.y)  //到达目标点
 62         {
 63             printf("%d
",t.step);
 64             return;
 65         }
 66         if(t.step&&t.step%p==0)  //光标移动一次
 67         {
 68             t.dir=(t.dir+3)%4;
 69         }
 70         if(vis[t.x][t.y][t.dir]) continue;
 71         vis[t.x][t.y][t.dir]=true;  //标记访问过
 72 
 73         s.x=t.x+dx[t.dir];  //往前移动
 74         s.y=t.y+dy[t.dir];
 75         s.step=t.step+1;
 76         s.dir=t.dir;
 77         if(s.x>=0&&s.x<n&&s.y>=0&&s.y<m&&mp[s.x][s.y]!='*')
 78         {
 79             q.push(s);
 80         }
 81 
 82         s.x=t.x;    //原地不动 
 83         s.y=t.y;
 84         s.step=t.step+1;
 85         s.dir=t.dir;
 86         q.push(s);
 87 
 88         s.x=t.x;   //光标向右移
 89         s.y=t.y;
 90         s.step=t.step+1;
 91         s.dir=(t.dir+1)%4;
 92         q.push(s);
 93 
 94         s.x=t.x;  //光标向左移
 95         s.y=t.y;
 96         s.step=t.step+1;
 97         s.dir=(t.dir+3)%4;
 98         q.push(s);
 99     } 
100     puts("YouBadbad");   //找不到目标点  退出
101 }
102 
103 int main()
104 {
105    //Read();
106    //Write();
107    int t;
108    scanf("%d",&t);
109    while(t--)
110    {
111        scanf("%d%d%d",&n,&m,&p);
112        for(int i=0;i<n;i++)
113         scanf("%s",mp[i]);
114        for(int i=0;i<n;i++)
115         for(int j=0;j<m;j++)
116        {
117            if(mp[i][j]=='@')
118            {
119                s.x=i;
120                s.y=j;
121            }
122            if(mp[i][j]=='$')
123            {
124                e.x=i;
125                e.y=j;
126            }
127        }
128        memset(vis,0,sizeof(vis));
129        bfs();
130    }
131     return 0;
132 }