【noip模拟赛1】古韵之鹊桥相会

描述

迢迢牵牛星,皎皎河汉女。

纤纤擢素手,札札弄机杼;

终日不成章,泣涕零如雨。

河汉清且浅,相去复几许?

盈盈一水间,脉脉不得语。

——《古诗十九首》

传说,上古时期的某个七月七日,王母娘娘为了阻止牛郎织女的爱情,划一道玉钗拆散鸳鸯,使两人“星桥鹊驾,经年才见,想离情、别恨难穷。”于是,“执子之手,与子偕老”成了天下有情人共同的希翼。

在气宇轩昂、玉树临风、才高八斗、英俊潇洒的程文大牛的期盼中,浪漫又迷人的七夕终于来临了。迷离的夜空之上,牛郎织女的絮语伴随着美好的秋光,浸润了古今文人墨客多情的心。他与美若天仙、唇红齿白、蕙质兰心、冰雪聪明的某MM约好在清江的小桥上相会……

天亦有情,此时,浮云错开,从天而降一张丝绸地图:正面上,不同颜色的星星组成了前方道路的俯视图;背面写着“愿有情人终成眷属,无伴者皆得幸福。——瑾姝”。

程文仔细看着这个图,发现自己必须从上到下打通一条道路才能见到某MM,于是程文决定用排云掌和风神腿打开前方的道路——

现用不同的字母来表示不同颜色的星星,连在一起(水平或竖直相邻才算连在一起)的相同颜色的星星,程文可以一次性全部打掉。图样如下:

AABBCCD

AFFBGGD

IIJBKKD

MNNOOPD

QQRRSST

比如在这张地图中,程文可以先打掉最右边的D区域,然后再打通T区域,这样就只用两次就可以打通道路(道路是可以拐弯的,不一定要是一条直线)。

因为使用排云掌和风神腿会耗费体力,耗费干净了程文就没法陪MM一起玩了,所以程文想用最少的次数来打通这条道路,不过程文现在跑去学Java了,这件事就交给你了。

输入

第一行有两个整数,m和n(0<m,n<21);

下面m行,每行n个字母。

输出

一个整数,程文打通道路用功力的最少的次数。

输入样例 1 

5 7 
AABBCCD
AFFBGGD
IIJBKKD
MNNOOPD
QQRRSST

输出样例 1

2

题解:

经典的一道最短路模版题,将地图中相邻且相同的点距离为0,不相同为1,然后建立两个假点,源点s和最上面一排所有点相连,距离为0;同样的,汇点t和最下面一排所有点相连,距离也为0;接下来就是求s到t的最短路ans,输出ans+1即为答案。

同时,注意到地图范围是20*20,BFS暴搜也可以过。

//
//  main.cpp
//
//
//  Created by Edwin on 2019/2/25.
//  Copyright &#169; 2019 Edwiv. All rights reserved.
//
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define eps 1e-8
#define PI acos(-1.0)
#define mst(a,b) memset(a,b,sizeof(a))
#define FF(i,a) for(int i=0;i<a;++i)
#define FORD(i,a,b) for(int i=a;i>=b;--i)
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define sc(t) scanf("%d",&(t))
#define sc2(t,x) scanf("%d%d",&(t),&(x))
#define pr(t) printf("%d\n",(t))
#define pb push_back
#define quickcin ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define lson rt<<1
#define rson rt<<1|1
#define delf (l+r)>>1
#define lowbit(x) (x&-x)
const int maxn=2000;
using namespace std;
int n,m;
char Map[maxn][maxn];
int d[maxn],c[maxn];
bool vis[maxn];
int dirx[4]={1,-1,0,0};
int diry[4]={0,0,1,-1};
int check(int x,int y){
    if(x<0||x>=n||y<0||y>=m)
        return 0;
    return 1;
}
struct edge{
    int v,w,nxt;
}e[maxn];
int tot,head[maxn];
void init(){
    mst(head,-1);
    tot = 0;
}
void addedge(int u,int v,int w){
    e[tot] = {v,w,head[u]}; head[u] = tot++;
}
int Spfa(int s,int n){
    int u,v,w;
    queue <int> q;
    mst(d,INF);mst(c,0);mst(vis,0);
    d[s]=0;
    q.push(s); vis[s]=1; c[s]=1;
    while(!q.empty()){
        u=q.front(); q.pop(); vis[u]=0;
        for(int k=head[u]; k!=-1; k=e[k].nxt){
            v=e[k].v, w=e[k].w;
            if( d[u]+w < d[v]){
                d[v]=d[u]+w;
                if(!vis[v]){
                    q.push(v); vis[v]=1;
                    if(++c[v]>n)
                        return 0;
                }
            }
        }
    }
    return 1;
}

int main(){
    sc2(n,m);
    getchar();
    init();
    FF(i,n){
        FF(j,m){
            scanf("%c",&Map[i][j]);
        }
        getchar();
    }
    FF(i,n){
        FF(j,m){
            for(int k=0;k<4;++k){
                int tox=i+dirx[k];
                int toy=j+diry[k];
                if(check(tox,toy)){
                    if(Map[tox][toy]==Map[i][j])
                        addedge(i*m+j+1,tox*m+toy+1,0);
                    else
                        addedge(i*m+j+1,tox*m+toy+1,1);
                }
            }
        }
    }
    int s=0;
    int t=n*m+1;
    for(int i=0;i<m;++i){
        addedge(s,i+1,0);
        addedge((n-1)*m+i+1,t,0);
    }
    Spfa(s,n*m+2);
    printf("%d\n",d[t]+1);
    return 0;
}

 

发表评论,支持MarkDown语法