NC25001. [USACO 2008 Ope B]Munching
描述
Bessie loves her grass and loves to hurry to the barn for her evening milking session. She has partitioned the pasture into a rectilinear grid of R (1 <= R <= 100) rows and C (1 <= C <= 100) columns and marked the squares as grass or rocky (she can't eat rocks and won't even go into those squares). Bessie starts on her map at location Rb,Cb and wishes to munch her way, square by square, to the barn at location 1,1 by the shortest route possible. She moves from one square to any one of the potentially four adjacent squares. Below is the original map [with rocks ('*'), grass ('.'), the barn ('B'), and Bessie ('C' for cow) at row 5, col 6] and a route map with the optimal route marked with munches ('m'): Map Optimal Munched Route 1 2 3 4 5 6 <-col 1 2 3 4 5 6 <-col 1 B . . . * . 1 B m m m * . 2 . . * . . . 2 . . * m m m 3 . * * . * . 3 . * * . * m 4 . . * * * . 4 . . * * * m 5 * . . * . C 5 * . . * . m Bessie munched 9 squares. Given a map, determine how many squares Bessie will eat on her shortest route to the barn (there's no grass to eat on the barn's square).输入描述
* Line 1: Two space-separated integers: R and C
* Lines 2..R+1: Line i+1 describes row i with C characters (and no spaces) as described above
输出描述
* Line 1: A single integer that is the number of squares of grass that Bessie munches on the shortest route back to the barn
示例1
输入:
5 6 B...*. ..*... .**.*. ..***. *..*.C
输出:
9
C++(clang++11) 解法, 执行用时: 4ms, 内存消耗: 504K, 提交时间: 2021-02-08 22:39:51
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,q[10010][5],f[110][110],x2[4]={0,0,-1,1},y2[4]={-1,1,0,0};
char ch[110][110];
int main()
{
int n,m,c,d;
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
cin>>ch[i][j];
if(ch[i][j]=='C')
{
ch[i][j]='.';
c=i;
d=j;
}
if(ch[i][j]=='B')
{
q[1][0]=i;
q[1][1]=j;
}
}
int s=0,w=1;
while(s<w)
{
s++;
int x=q[s][0],y=q[s][1],z=q[s][2];
if(x==c&&y==d)
{
cout<<z<<"\n";
return 0;
}
for(int i=0;i<4;i++)
{
int x1=x+x2[i],y1=y+y2[i];
if(x1<1||y1<1||x1>n||y1>m||ch[x1][y1]=='*'||f[x1][y1])
continue;
w++;
q[w][0]=x1;
q[w][1]=y1;
q[w][2]=z+1;
f[x1][y1]=true;
}
}
}