远处的牧场Distant Pastures

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：

好多天没写题解了。

题目

自己看看吧点这里

思路

不要看它是字符串，其实很水。看完题目了之后先是想到了最短路找最大的一条路径。
突然想起了BFS与最短路之间不可描述的关系，最后蒟蒻打了一个又像SPFA又像BFS的东西。但在写代码时也是要注意好一些小细节！

注意好起点不一定是（1,1）点，还可能是其他点，脑中蹦出来TLE的感觉，看了一眼范围才注意到不必担心。那就开始了打代码的快乐时光。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<bits/stdc++.h>//万能头文件
using namespace std;
struct node{
    int x,y;
};//存当前的坐标
int n,a,b;long long dis[101][101],ans;
char s[101][101]; int mv[4][2]={{1,0},{-1,0},{0,-1},{0,1}};//扩展节点四个方向
bool mapp[101][101];//标记是否在队列之中
void BFS(int sx,int sy){
    queue<node>que; memset(dis,0x7f7f7f7f,sizeof(dis));
    memset(mapp,0,sizeof(mapp));//注意初始化
    mapp[sx][sy]=1; que.push((node){sx,sy}); dis[sx][sy]=0;
    while(que.size()){//开始了我们的最短路之旅
        node d=que.front(); que.pop(); mapp[d.x][d.y]=0;//取出队首
        for(int i=0;i<4;i++){//扩展节点
            int tx=mv[i][0]+d.x;
            int ty=mv[i][1]+d.y;
            if(tx>0&&tx<=n&&ty>0&&ty<=n){//是否符合地图范围
                int t;
                if(s[tx][ty]==s[d.x][d.y]) t=a;
                else t=b;//看当前与扩展点是否相同
                if(dis[tx][ty]>dis[d.x][d.y]+t){//松弛操作
                    dis[tx][ty]=dis[d.x][d.y]+t;
                    if(mapp[tx][ty]==0) mapp[tx][ty]=1,que.push((node){tx,ty});
                }//不在队列之中要放入队列
            }
        }
    }
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    ans=max(ans,dis[i][j]);//在整个地图中找最大的最短路
}
int main(){
    cin>>n>>a>>b;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    cin>>s[i][j];//输入
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    BFS(i,j);//不断枚举开始点
    cout<<ans<<endl;//输出
    return 0;
}

最后说几句，看到这种题不必担心，不会就暴力点，总是会有分的。但之后有想法来改进那是一定要来尝试一下。

蒟蒻表示又水了一天，开心。