Zoj 3865 Superbot

按规则移动机器人 , 问是否能拾得宝藏 。 

加了一个控制板 , 还增加了一个控制板移动周期 p 

将移动周期变换一下 , 移动一次  就相当于光标向左不耗费时间的移动了一格

搜索思路 : 搜索当前格子到上下左右四个格子所花费的最短时间 。

记录光标的信息 , 和当前格子所需最短时间 。

bfs + bfs

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 #define PI acos(-1.0)
  4 #define MAXN 20
  5 #define INF 0x3f3f3f3f
  6 int p,min_num;
  7 int n,m;
  8 int G[MAXN][MAXN];
  9 int dir[4][2]={{0,-1},{0,1},{-1,0},{1,0}};
 10 struct point
 11 {
 12     int x;
 13     int y;
 14 }start,pos;
 15 struct base
 16 {
 17     int cnt;
 18     int t;
 19 }step[MAXN][MAXN];
 20 int read_ch(int x, int y)
 21 {
 22     char ch;
 23     while(ch = getchar())
 24     {
 25         if(ch == '@')
 26         {
 27             start.x=x;
 28             start.y=y;
 29             return true;
 30         }
 31         if(ch == '.') return true;
 32         if(ch == '$')
 33         {
 34             pos.x=x;
 35             pos.y=y;
 36             return true;
 37         }
 38         if(ch == '*') return false;
 39     }
 40 }
 41 void show()
 42 {
 43     for(int i = 1 ; i <= n ; i ++,cout<<endl)
 44         for(int j = 1 ; j <= m ; j ++)
 45             printf(step[i][j].cnt == INF?"INF ":"%3d ", step[i][j].cnt);
 46     cout<<endl;
 47 }
 48 int bfs(int t,int cnt,int pos)
 49 {
 50     queue <int> Q;
 51     int temp=0;
 52     Q.push(cnt);
 53     Q.push(temp);
 54     while(!Q.empty())
 55     {
 56         int x=Q.front();
 57         Q.pop();
 58         temp=Q.front();
 59         Q.pop();
 60 
 61         if(((t+temp) % p == 0) && (t + temp)) x = (x + 3) % 4;
 62 
 63         Q.push((x+3)%4);
 64         Q.push(temp+1);
 65 
 66         Q.push(x);
 67         Q.push(temp+1);
 68 
 69         Q.push((x+1)%4);
 70         Q.push(temp+1);
 71 
 72         if(x == pos) return t+temp+1;
 73     }
 74     return INF;
 75 }
 76 void _bfs()
 77 {
 78     memset(step,0x3f,sizeof(step));
 79     step[start.x][start.y].cnt=0;
 80     step[start.x][start.y].t=0;
 81     queue <int> Q;
 82     Q.push(start.x);
 83     Q.push(start.y);
 84     while(!Q.empty())
 85     {
 86         int x = Q.front();
 87         Q.pop();
 88         int y = Q.front();
 89         Q.pop();
 90 
 91         if(x < 1 || x > n || y < 1 || y > m || !G[x][y]) continue;
 92 
 93         for(int i=0;i<4;i++)
 94         {
 95             int xx = x + dir[i][0];
 96             int yy = y + dir[i][1];
 97 
 98             if(xx < 1 || xx > n || yy < 1 || yy > m || !G[xx][yy]) continue;
 99 
100             int temp = bfs(step[x][y].t,step[x][y].cnt,i);
101             if(temp < step[xx][yy].t)
102             {
103                 step[xx][yy].t = temp;
104                 step[xx][yy].cnt = i;
105                 Q.push(xx);
106                 Q.push(yy);
107                 //printf("x:%2d y:%2d cnt:%2d xx:%2d yy:%2d \n",x,y,i,xx,yy);
108                 //show();
109             }
110         }
111     }
112 }
113 int main()
114 {
115     int T;
116     scanf("%d",&T);
117     while(T--)
118     {
119         scanf("%d %d %d",&n,&m,&p);
120         memset(G,false,sizeof(G));
121         for(int i=1;i<=n;i++)
122             for(int j=1;j<=m;j++)
123             G[i][j]=read_ch(i,j);
124         _bfs();
125         printf(step[pos.x][pos.y].t != INF?"%d\n":"YouBadbad\n",step[pos.x][pos.y].t);
126     }
127     return 0;
128 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Uva_10253 Series-Parallel Networks

        2:G1,G2为串并联网络, 将它们的源点与汇点分别连接起来, 得到的也是串并联网络(并联)

    若羽
  • LightOj_1284 Lights inside 3D Grid

      给一个X * Y * Z 的立方体, 每个单位立方体内都有一盏灯, 初始状态是灭的, 你每次操作如下:

    若羽
  • Hdu 1789 Doing Homework again

    Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Othe...

    若羽
  • 洛谷P4779 【模板】单源最短路径(标准版)

    前几天写dijkstra的时候没打vis标记居然A了,然后天真的我就以为Dijkstra不用打标记。

    attack
  • codeforces 580C(dfs)

    给一棵n个节点树,某个结点可能会打上标记,从根节点走,问有几条路径上的连续标记树不超过m。

    dejavu1zz
  • cctype

    在头文件<ctype.h>中定义了一些测试字符的函数。在这些函数中,每个函数的参数都是整型int,而每个参数的值或者为EOF,或者为char类型的字符。<cty...

    猿人谷
  • 1038 统计同成绩学生 (20 分)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    韩旭051
  • Codeforces Round 767C 树形结构求子树和

    很容易发现每一颗子树的点权是固定的,因为总和固定,设每一部分的大小为W,那么我们就从下往上更新,遇到等于W的子树就sz重置成0.

    用户2965768
  • 从Bitmap中获取YUV数据的两种方式

    从Bitmap中我们能获取到的是RGB颜色分量,当需要获取YUV数据的时候,则需要先提取R,G,B分量的值,然后将RGB转化为YUV(根据具体的YUV的排列格式...

    雪月清
  • poj1251 Jungle Roads Kruskal算法+并查集

    风骨散人Chiam

扫码关注云+社区

领取腾讯云代金券