175. 电路维修(bfs)

蔚落 2021-11-11 03:36 291阅读 0赞

题目链接：[https://www.acwing.com/problem/content/description/177/][https_www.acwing.com_problem_content_description_177]

达达是来自异世界的魔女，她在漫无目的地四处漂流的时候，遇到了善良的少女翰翰，从而被收留在地球上。

翰翰的家里有一辆飞行车。

有一天飞行车的电路板突然出现了故障，导致无法启动。

电路板的整体结构是一个R行C列的网格（R,C≤500），如下图所示。

电路.png

每个格点都是电线的接点，每个格子都包含一个电子元件。

电子元件的主要部分是一个可旋转的、连接一条对角线上的两个接点的短电缆。

在旋转之后，它就可以连接另一条对角线的两个接点。

电路板左上角的接点接入直流电源，右下角的接点接入飞行车的发动装置。

达达发现因为某些元件的方向不小心发生了改变，电路板可能处于断路的状态。

她准备通过计算，旋转最少数量的元件，使电源与发动装置通过若干条短缆相连。

不过，电路的规模实在是太大了，达达并不擅长编程，希望你能够帮她解决这个问题。  
输入格式

输入文件包含多组测试数据。

第一行包含一个整数T，表示测试数据的数目。

对于每组测试数据，第一行包含正整数R和C，表示电路板的行数和列数。

之后R行，每行C个字符，字符是"/“和”"中的一个，表示标准件的方向。  
输出格式

对于每组测试数据，在单独的一行输出一个正整数，表示所需的缩小旋转次数。

如果无论怎样都不能使得电源和发动机之间连通，输出NO SOLUTION。  
数据范围

1≤R,C≤500  
,  
1≤T≤5

输入样例：

1  
3 5  
\\/\\  
\\///  
/\\\\

输出样例：

样例解释

样例的输入对应于题目描述中的情况。

只需要按照下面的方式旋转标准件，就可以使得电源和发动机之间连通。

电路2.png

分析：  
这个题有点考验思维了。必须好好的理解。  
我们要考虑的是最后到终点的距离，终点是（R，C），起点是（0，0）；  
注意终点不是最后一个单元格，而是最后一个角（即最后一个单元格的右下角）。  
所以，我们并不是按单元格来计算距离，而是按两个直线相交的角来计算。  
所以，我的dp\[i\]\[j\].表示的是（0，0）到（i，j)这个角的最少距离是多少。  
同时我们需要考虑的是（0，0）到（i，j）这个角经过的单元格里面的‘/’和‘\\’。  
想象一下这个过程，如果我要从（0，0）到（1，1）这个角。那我经过的单元格就是Graph\[1\]\[1\]，同时（0，0）到（1，1）这个角应该是‘\\’。所以我们判断一下Graph\[1\]\[1\]是否等于’\\ ‘。如果是，则距离为0，不然为1.  
在考虑一下（1，1）到（2，0）这个角。我经过的单元格应该是Graph\[2\]\[1\]，同时，这个单元格里面的内容应该为’/’。如果是，则距离为0，不然为1.  
同理，其他方向。  
我们找到其中的规律，并把其作为方向变量即可。  
总之一点，不能在像平常那样理解数组下标的意义。  
dp\[i\]\[j\]表示的是角。

最后，这差不多就是一个最短路问题了。  
我们每次应该选择距离最小的去不断更新即可。因为这个题，只有两种距离权值（0或者1）。所以我们可以直接用一个双端队列即可。有点dijiskla的思想吧。  
同时注意我们不可以直接用vis\[i\]\[j\]数组来标记是否访问过。  
想象一下  
dp\[i\]\[j\] 是0，dp\[i-2\]\[j\]也是0.  
从dp\[i\]\[j\]到dp\[i-1\]\[j+1\]的距离为1  
从dp\[i-2\]\[j\]到dp\[i-1\]\[j+1\]的距离为0.  
可是我在更新的时候，更新了dp\[i\]\[j\]到dp\[i-1\]\[j+1\].并且把vis\[i-1\]\[j+1\]标记为访问过了，那我就不会再继续更新dp\[i-2\]\[j\]到dp\[i-1\]\[j+1\]了。  
因为是双端队列，所以是可能存在这种情况的。

#include"stdio.h"
    #include"string.h"
    #include"deque"
    #include"algorithm"
    using namespace std;
    #define INF 1001010
    typedef pair<int,int> PII;
    
    const int dir1[4][2] = {
       {1,1},{-1,-1},{-1,1},{1,-1}};
    const int dir2[4][2] = {
       {1,1},{0,0},{0,1},{1,0}};
    int T,R,C;
    char Graph[510][510];
    int vis[510][510];
    int dp[510][510];
    int minx;
    
    int check(int a,int b)
    {
         if(a >= 0 && a <= R && b >= 0 && b <= C)
                return 1;
        return 0;
    }
    
    void bfs()
    {
        deque<PII> Q;
        Q.push_front({0,0});
        vis[0][0] = 1;
        dp[0][0] = 0;
        while(!Q.empty())
        {
            PII T = Q.front(); Q.pop_front();
            int x = T.first,y = T.second;
            for(int i = 0; i < 4; i ++)
            {
                int x1 = x + dir1[i][0],y1 = y + dir1[i][1];
                int a = x + dir2[i][0],b = y + dir2[i][1];
                if(check(x1,y1) == 0) continue;
                int time = (Graph[a][b] != (i <= 1 ? '\\' : '/'));
                if( dp[x1][y1] <= dp[x][y] + time ) continue;
               // vis[x1][y1] = 1;
                dp[x1][y1] = dp[x][y] + time;
                //printf("a = %d b = %d x = %d y = %d x1 = %d y1 = %d dp[x][y] = %d time = %d\n",a,b,x,y,x1,y1,dp[x][y],time);
                if(time == 0)
                Q.push_front({x1,y1});
                else
                Q.push_back({x1,y1});
            }
        }
        return ;
    }
    
    int main()
    {
        scanf("%d",&T);
        while(T --)
        {
            scanf("%d%d",&R,&C);
            memset(vis,0,sizeof(vis));
            for(int i = 0; i <= R;i ++)
                for(int j = 0; j <= C; j ++)
                   dp[i][j] = INF;
            for(int i = 1; i <= R; i ++)
                scanf("%s",Graph[i] + 1);
             bfs();
    
            if(dp[R][C] == INF)
                 printf("NO SOLUTION\n");
            else
                printf("%d\n",dp[R][C]);
        }
    }

[https_www.acwing.com_problem_content_description_177]: https://www.acwing.com/problem/content/description/177/