P2937 [USACO09JAN]激光电话Laserphones

· · 题解

很有意思的一道题，做法不是很难。但是卡住了机房大佬

理论分析

模拟一下走的过程。

第一次走的时候我们到起点的上下左右四个方向都需要0个镜子，我们把这些点都记录成第一次的扩展。

//拿样例来举个栗子，不妨设上面的C是起点，另一个是终点
....... 
......C 
......* 
*****.* 
....*.. 
....*.. 
.C..*.. 
.......

那么我们标记出第一次可以确定的点

......1 
111111C 
......* 
*****.* 
....*.. 
....*.. 
.C..*.. 
.......

所有被标记为1的点，都不需要平面镜，我们接着走第二步。

第二步我们把所有标记为1的点进行同样的操作，把这些点的上下左右扩展出来，记录成第二步扩展

2222221 
111111C 
222222* 
*****2* 
....*2. 
....*2. 
.C..*2. 
.....2.

所有被标记为2的点，都需要1个平面镜。

... ...

像这样我们不断地扩展下去，就会得到到C点所需的镜子个数 0.0

代码实现

首先这种跑地图还问你最短xx的，我们就可以上bfs了。

设计一个结构体

struct node{
    int x,y;//点坐标
    int num;//记录这个点是第几步扩展得来的
}s,t;

然后随手瞎敲一下bfs就行了

void bfs(){
    while(!q.empty()){
        node u=q.front(),v=u;//u和v都是队首
        q.pop();
        u.num++;
        v=u; v.x=u.x-1;//上 
        dfs(1,v);
        v=u; v.x=u.x+1;//下 
        dfs(2,v);
        v=u; v.y=u.y-1;//左 
        dfs(3,v);
        v=u; v.y=u.y+1;//右 
        dfs(4,v);
    }
}

用这个bfs扩展队首点的四个方向，每次dfs去进行染色的工作

void dfs(int fx,node u){ //fx记录方向（1上2下3左4右） u为当前所在点 
    int x=u.x,y=u.y,p=u.num; 
    if(a[x][y]<p || a[x][y]==inf) return;//如果该点标记比这次扩展的小【即更优】，就直接跳过它。
                                        //inf表示墙，返回
    if(x<1 || y<1 || x>n || y>m) return;//超出边界返回
    if(fx==1){
        a[x][y]=p;//染色
        q.push((node){x,y,p});//放入队列，之后进行拓展
        dfs(1,(node){x-1,y,p});//染下一个上边的点
    }
    if(fx==2){
        a[x][y]=p;
        q.push((node){x,y,p});
        dfs(2,(node){x+1,y,p});
    }
    if(fx==3){
        a[x][y]=p;
        q.push((node){x,y,p});
        dfs(3,(node){x,y-1,p});
    }
    if(fx==4){
        a[x][y]=p;
        q.push((node){x,y,p});
        dfs(4,(node){x,y+1,p});
    }
}

说明：我把数据给出的地图转成了int类型，inf代表墙。

完整代码如下~

#include<bits/stdc++.h>
#include<queue>
#define inf 0x3f3f3f3f
using namespace std;
int n,m;
int a[110][110];//保存地图
struct node{
    int x,y;
    int num;
}s,t;
queue<node> q;
void dfs(int fx,node u){ //fx记录方向（1上2下3左4右） u为当前所在点 
    int x=u.x,y=u.y,p=u.num; 
    if(a[x][y]<p || a[x][y]==inf) return;
    if(x<1 || y<1 || x>n || y>m) return;

    if(fx==1){
        a[x][y]=p;
        q.push((node){x,y,p});
        dfs(1,(node){x-1,y,p});
    }
    if(fx==2){
        a[x][y]=p;
        q.push((node){x,y,p});
        dfs(2,(node){x+1,y,p});
    }
    if(fx==3){
        a[x][y]=p;
        q.push((node){x,y,p});
        dfs(3,(node){x,y-1,p});
    }
    if(fx==4){
        a[x][y]=p;
        q.push((node){x,y,p});
        dfs(4,(node){x,y+1,p});
    }
}

void bfs(){
    while(!q.empty()){
        node u=q.front(),v=q.front();
        q.pop();
        u.num++;
        v=u; v.x=u.x-1;//上 
        dfs(1,v);
        v=u; v.x=u.x+1;//下 
        dfs(2,v);
        v=u; v.y=u.y-1;//左 
        dfs(3,v);
        v=u; v.y=u.y+1;//右 
        dfs(4,v);
    }
}
int main(){
    cin>>m>>n;
    char zwh;
    memset(a,inf,sizeof(a));
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++) a[i][j]=inf-1;
    //如果地图范围全部是比答案小的数字（比如0），那么在dfs染色的时候就会直接返回，导致错误。
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf(" %c",&zwh);
            if(zwh=='C'){
                if(s.x) t.x=i,t.y=j,t.num=0;//找到起点和终点
                else s.x=i,s.y=j,s.num=0;
            }
            if(zwh=='*'){
                a[i][j]=inf;
            }

        }
    }
    q.push(s);
    bfs();
    cout<<a[t.x][t.y]-1;//注意减一
    return 0;
}