zoj 4020 The 18th Zhejiang University Programming Contest Sponsored by TuSimple - G Traffic Light(广搜)
2024-08-22 16:39:45
题目链接:The 18th Zhejiang University Programming Contest Sponsored by TuSimple - G Traffic Light
题解:
题意自己翻译,此题首先肯定是要广搜的,不过要开一个1e5*1e5的数组好像有点困难,
所以用结构体来存每个点的下标,然后从源点开始广搜。定义一个pair<node,int>,第一个存节点信息,第二个存到当前节点的步数,因为还要处理到达每个节点的状态。
状态:走奇数步并且状态为1与走偶数步状态为0的结果是一样的,都是向左或向右移动。走偶数步并且状态为1与走奇数步状态为0的结果也是一样,可以向上或向下移动。
最后定义一个pair的队列。
代码:
#include <stdio.h> #include <iostream> #include <vector> #include <queue> #include <string.h> #include <utility> #define IO ios::sync_with_stdio(0);\ cin.tie();cout.tie(); using namespace std; ; struct node { int i,j,value; int flag; } res[N]; pair <node,int> p; queue <pair<node,int > > q; int main() { int T; cin >> T; while(T--) { memset(res,,sizeof(res)); ; cin >> n >> m; ; i <= n; i++) ; j <= m; j++) cin >> x,res[++num].value = x,res[num].i = i,res[num].j=j; int x1,y1,x2,y2; cin >>x1>>y1>>x2>>y2; ; res[(x1-)*m + y1].flag = ; p.first = res[(x1-)*m + y1]; p.second = sum; q.push(p); ,ff = ; while(!q.empty()) { pair <node,int> pp; pp = q.front(); q.pop(); int i = pp.first.i,j = pp.first.j,value = pp.first.value,sum = pp.second; if(i==x2&&j==y2) { ans = sum; ff = ; break; } )&&value==)||(!(sum&)&&value==)) { <=n&&res[i*m+j].flag==) { pp.first.i = i+,pp.first.j = j,pp.first.value = res[(i)*m+j].value; pp.first.flag = ; res[(i)*m+j].flag = ; pp.second = sum+; q.push(pp); } >&&res[(i-)*m+j].flag==) { pp.first.i = i-,pp.first.j = j,pp.first.value = res[(i-)*m+j].value; pp.first.flag = ; res[(i-)*m+j].flag = ; pp.second = sum+; q.push(pp); } } else { <=m&&res[(i-)*m+j+].flag==) { pp.first.i = i,pp.first.j = j+,pp.first.value = res[(i-)*m+j+].value; pp.first.flag = ; res[(i-)*m+j+].flag = ; pp.second = sum+; q.push(pp); } >&&res[(i-)*m+j-].flag==) { pp.first.i = i,pp.first.j = j-,pp.first.value = res[(i-)*m+j-].value; pp.first.flag = ; res[(i-)*m+j-].flag = ; pp.second = sum+; q.push(pp); } } } printf(); while(!q.empty())q.pop(); } ; } /* 4 2 3 1 1 0 0 1 0 1 3 2 1 2 3 1 0 0 1 1 0 1 3 1 2 2 2 1 0 1 0 1 1 2 2 1 2 0 1 1 1 1 1 */
最新文章
- ios app的版本号
- 《Head First 设计模式》之观察者模式
- Java项目多数据源配置
- FlASK中的endpoint问题
- CMD命令简单使用
- Docker与LXC的区别
- 新浪微博的账号登录及api操作
- mybatis 控制台打印sql
- WindowXP与WIN7环境安装、破解、配置AppScan8.0
- 使用SharedPreferences进行数据存储
- 【WPF学习日记——[DevExpress]】GridControl 行中使用按钮
- Remoting的入门教程
- CTL_CODE 宏 详解
- SWT的CheckBoxTreeView的上级菜单与下级菜单的选中的实现
- hdu 1068 Girls and Boys 最大独立点集 二分匹配
- python之常用模块二(hashlib logging configparser)
- ES6躬行记(9)——字符串
- css上传图片中等待不可点击效果
- 小白学习 Redis 数据库日记(2017-06-13)
- vue-awesome-swiper轮播的使用