这题面有点难理解, 建议直接跳到题意解释那一部分 (虽然我觉得解释的不大对, 但按照解释来做确实能 AC);
按照 "题意解释" 的思路来思考这个题, 那么就十分的简单了:
1. 首先要读入这个字符矩阵, 可以用 cin(会不会 TLE 不知道), 这里我用的是 getchar 读入;
2. 从'*'开始一遍广搜, 记录一下每个'#'被搜索到的时间, 直到所有的点都被遍历过;
3. 找出所有'#'的位置时间最大的那个, 就是第一问的答案, 暂且记为 much;
4. 因为走过的格子每单位时间会增加 1 点高度, 所以对于某一个格子 i, 若遍历它的最短时间是 ti, 那么它对答案作出的贡献就是: much - ti + 1, 将每个格子的贡献累加起来就是第二问的答案啦;
5. 考虑判断无解的情况: O(nm) 暴力扫一遍所有的格子, 如果出现了遍历时间为 0 的情况 (也就是说某个格子没有被遍历到), 说明无解;
代码如下:
- #include<iostream>
- #include<cstdio>
- #include<queue>
- #include<cmath>
- using namespace std;
- const int mod=19260817;
- char read() // 自定义字符读入
- {
- char ch=getchar();
- while(ch!='*'&&ch!='o'&&ch!='#') ch=getchar(); // 不是题目中的三种字符就一直往下读
- return ch;
- }
- struct juanzi // 开一个结构体, 存每一个格子的信息: 最先被遍历的时间是 t, 坐标是 (x1,y1)
- {
- int t,x1,y1;
- }b[250001];
- queue<juanzi> q; // 开一个结构体类型的队列
- char a[501][501]; // 存输入的字符矩阵
- int n,m,start,endd,xx,yy; //n*m 的矩阵, 打印机'*'的坐标是 (start,endd), 注意不要用 end, 好像会和 STL 里面的东西重名 (我 CE 我知道)
- int dx[5]={0,1,0,-1,0}; // 四个方向
- int dy[5]={0,0,-1,0,1};
- int vis[501][501]; // 存每个点被遍历的时间
- int ans,much;
- void bfs()
- {
- q.push((juanzi){0,start,endd}); // 起点入队
- juanzi f;
- while(!q.empty()) // 其实我们每一步都判断是否将所有点都遍历过, 只需判队列非空就好啦, 队列为空就说明无法再遍历到其他的点了
- {
- f=q.front();
- q.pop();
- for(int i=1;i<=4;i++)
- {
- xx=f.x1+dx[i]; // 往四个方向走
- yy=f.y1+dy[i];
- if(a[xx][yy]=='#'&&vis[xx][yy]==0) // 如果可以走并且之前没走过, 那就走
- {
- vis[xx][yy]=f.t+1; // 到这个格子的时间是上一个格子的时间再加一
- q.push((juanzi){f.t+1,xx,yy}); // 入队去遍历下面的格子
- }
- }
- }
- }
- int main()
- {
- scanf("%d%d",&n,&m);
- for(int i=1;i<=n;i++)
- for(int j=1;j<=m;j++)
- {
- a[i][j]=read();
- if(a[i][j]=='*') // 记录下打印机'*'的位置
- {
- start=i;
- endd=j;
- vis[i][j]=-1; // 把不能遍历的点的时间全赋成 - 1
- }
- if(a[i][j]=='o') vis[i][j]=-1; // 花盆的位置
- }
- bfs(); // 核心代码: 广度优先搜索
- for(int i=1;i<=n;i++) // 判无解的情况
- for(int j=1;j<=m;j++)
- if(vis[i][j]==0)
- {
- cout<<-1;return 0;
- }
- for(int i=1;i<=n;i++)
- for(int j=1;j<=m;j++)
- much=max(much,vis[i][j]); // 找最后被遍历到的点所需要的时间
- printf("%d\n",much);
- for(int i=1;i<=n;i++)
- for(int j=1;j<=m;j++)
- {
- if(vis[i][j]>0) // 排除了打印机'*'和花盆'o'的位置
- {
- ans=(ans+(much-vis[i][j]+1)%mod)%mod; // 每个格子的贡献
- }
- }
- printf("%d",ans);
- return 0;
- }
- /*
- 其实由于数据有锅, 无解的情况没有看出来, 当成有解的情况做了;
- AC 代码要注释掉那个判断无解的情况 QwQ~
- 但加上那一段判无解的代码应该才是最正确的
- */
来源: http://www.bubuko.com/infodetail-3107392.html