Cheese Aizu - 0558 (搜索题)
Time limit8000 ms
Memory limit131072 kB
チーズ ()
問題
今年も JOI 町のチーズ工場がチーズの生産を始め,ねずみが巣から顔を出した.JOI 町は東西南北に区画整理されていて,各区画は巣,チーズ工場,障害物,空き地のいずれかである.ねずみは巣から出発して全てのチーズ工場を訪れチーズを 1 個ずつ食べる.
この町には,N 個のチーズ工場があり,どの工場も1種類のチーズだけを生産している.チーズの硬さは工場によって異なっており,硬さ 1 から N までのチーズを生産するチーズ工場がちょうど 1 つずつある.
ねずみの最初の体力は 1 であり,チーズを 1 個食べるごとに体力が 1 増える.ただし,ねずみは自分の体力よりも硬いチーズを食べることはできない.
ねずみは,東西南北に隣り合う区画に 1 分で移動することができるが,障害物の区画には入ることができない.チーズ工場をチーズを食べずに通り過ぎることもできる.すべてのチーズを食べ終えるまでにかかる最短時間を求めるプログラムを書け.ただし,ねずみがチーズを食べるのにかかる時間は無視できる.
入力
入力は H+1 行ある.1 行目には 3 つの整数 H,W,N (1 ≤ H ≤ 1000,1 ≤ W ≤ 1000,1 ≤ N ≤ 9) がこの順に空白で区切られて書かれている.2 行目から H+1 行目までの各行には,'S','1', '2', ..., '9','X','.' からなる W 文字の文字列が書かれており,各々が各区画の状態を表している.北から i 番目,西から j 番目の区画を (i,j) と記述することにすると (1 ≤ i ≤ H, 1 ≤ j ≤ W),第 i+1 行目の j 番目の文字は,区画 (i,j) が巣である場合は 'S' となり,障害物である場合は 'X' となり,空き地である場合は '.' となり,硬さ 1, 2, ..., 9 のチーズを生産する工場である場合はそれぞれ '1', '2', ..., '9' となる.入力には巣と硬さ 1, 2, ..., N のチーズを生産する工場がそれぞれ 1 つずつある.他のマスは障害物または空き地であることが保証されている.ねずみは全てのチーズを食べられることが保証されている.
出力
すべてのチーズを食べ終えるまでにかかる最短時間(分)を表す整数を 1 行で出力せよ.
入出力例
入力例 1
3 3 1
S..
...
..1
出力例 1
4
入力例 2
4 5 2
.X..1
....X
.XX.S
.2.X.
出力例 2
12
入力例 3
10 10 9
.X...X.S.X
6..5X..X1X
...XXXX..X
X..9X...X.
8.X2X..X3X
...XX.X4..
XX....7X..
X..X..XX..
X...X.XX..
..X.......
出力例 3
91
問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。
题意:老鼠吃奶酪,吃能吃小于等于体力值的,吃奶酪加体力
题解:bfs,从1到n逐次使用bfs
#include<iostream>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<cmath>
#include<cstdlib>
#include<queue>
using namespace std;
#define INF 0x3f3f3f3f
const int maxn=; int dir[][]={,,-,,,,,-};
int sj[][];
char maze[][];
bool vis[][];
typedef pair<int,int>P;
int h,w,n,ti=; int bfs(int oi,int oj)
{
queue<P> que;
que.push(P(oi,oj));
P p;
while(que.size())
{
p=que.front();
que.pop();
if(maze[p.first][p.second]-''==n && ti==n)
return sj[p.first][p.second];
if(maze[p.first][p.second]-''==ti)
{
memset(vis,false,sizeof(vis));
vis[p.first][p.second]=true;
while(que.size())
{
que.pop();
}
maze[p.first][p.second]='.';
ti++;
}
for(int i=;i<;i++)
{
int xx,yy;
xx=p.first+dir[i][];
yy=p.second+dir[i][];
if(xx>= && xx<h && yy>= && yy<w && maze[xx][yy]!='X' && vis[xx][yy]==false )
{
vis[xx][yy]=true;
sj[xx][yy]=sj[p.first][p.second]+;
que.push(P(xx,yy));
}
} }
return sj[n][n];
} int main()
{
memset(sj,,sizeof(sj));
memset(vis,false,sizeof(vis));
cin>>h>>w>>n;
int i,j,an;
for(int i=;i<h;i++)
for(int j=;j<w;j++)
cin>>maze[i][j];
for(int i=;i<h;i++)
for(int j=;j<w;j++)
{
if(maze[i][j]=='S')
{
vis[i][j]=true;
an=bfs(i,j);
cout<<an<<endl;
return ;
}
}
}
最新文章
- C#开发微信门户及应用(17)-微信企业号的通讯录管理开发之部门管理
- java的Spring
- EF架构~XMLRepository仓储的实现
- thinkphp中assign()和display()区别和用法
- 如何用SQL命令行工具删除dedecms指定id文章
- sql 通过游标 拆分xml结构
- Linux vim的安装和配置:
- oracle 删除表和数据分析语句
- SQLite多线程写锁文件解决方案
- Kinetic使用注意点--container
- easyui dataBox 增加一天,减少一天
- Dynamics CRM:Word Template Feature 的使用和实际遇到问题解决方案
- Caffe可视化之VisualDL
- linux系统下Apache日志分割(按天生成文件)
- java mongodb连接配置实践——生产环境最优
- cJSON学习笔记 续集
- pandas 索引与列相互转化
- sql语句中避免使用mysql函数,提升mysql处理能力。
- HDU 1083 Courses 【二分图完备匹配】
- 容器基础(五): 实现一个简单容器sdocker
热门文章
- (转)nginx利用geo模块做限速白名单以及geo实现全局负载均衡的操作记录
- DOCKER启动失败Job for docker.service failed because the control process exited with error code. See ";syste mctl status docker.service"; and ";journalctl -xe"; for details.
- Java中的日志框架
- jquery 一键复制到剪切板
- RSA加密解密(转)
- SpringBoot服务监控
- mysql-练级查询
- BZOJ 3992: [SDOI2015]序列统计 NTT+快速幂
- MyEclipse7.0 M1下载和注册码
- Tarjan的学习笔记 求割边求割点