Cheese Aizu - 0558 （搜索题）

time limit8000 ms

memory limit131072 kb

 

チーズ ()

問題

今年も joi 町のチーズ工場がチーズの生産を始め，ねずみが巣から顔を出した．joi 町は東西南北に区画整理されていて，各区画は巣，チーズ工場，障害物，空き地のいずれかである．ねずみは巣から出発して全てのチーズ工場を訪れチーズを 1 個ずつ食べる． 

この町には，n 個のチーズ工場があり，どの工場も１種類のチーズだけを生産している．チーズの硬さは工場によって異なっており，硬さ 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=105;

int dir[4][2]={1,0,-1,0,0,1,0,-1};
int sj[1005][1005];
char maze[1005][1005];
bool vis[1005][1005];
typedef pair<int,int>p;
int h,w,n,ti=1;

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]-'0'==n && ti==n)
            return sj[p.first][p.second];
        if(maze[p.first][p.second]-'0'==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=0;i<4;i++)
        {
            int xx,yy;
            xx=p.first+dir[i][0];
            yy=p.second+dir[i][1];
            if(xx>=0 && xx<h && yy>=0 && yy<w && maze[xx][yy]!='x' && vis[xx][yy]==false )
            {
                vis[xx][yy]=true;
                sj[xx][yy]=sj[p.first][p.second]+1;
                que.push(p(xx,yy));
            }
        }
        
    }
    return sj[n][n];
}


int main()
{
    memset(sj,0,sizeof(sj));
    memset(vis,false,sizeof(vis));
    cin>>h>>w>>n;
    int i,j,an;
    for(int i=0;i<h;i++)
        for(int j=0;j<w;j++)
            cin>>maze[i][j];
    for(int i=0;i<h;i++)
        for(int j=0;j<w;j++)
        {
            if(maze[i][j]=='s')
            {
                vis[i][j]=true;
                an=bfs(i,j);
                cout<<an<<endl;
                return 0;
            }
        }
}