问题 A: 电路维修

时间限制: 1 Sec 内存限制: 128 MB
提交: 16 解决: 7
[提交][状态][讨论版][命题人:add_shengjunjie][Edit] [TestData]

题目链接：http://acm.ocrosoft.com/problem.php?cid=1694&pid=0

题目描述

Ha’nyu是来自异世界的魔女,她在漫无目的的四处漂流的时候,遇到了善良的少女Rika，从而被收留在地球上。Rika家里有一辆飞行车。有一天飞行车的电路板突然出现了故障，导致无法正常启动。

电路板的整体结构是一个R行C列的网格，如图所示。每一个格点都是电线的接点。每个格子都包含一个电子元件。电子元件的主要部分是一个可旋转的，连接一条对角线上的两个连接点的短电缆。在旋转之后，它就可以连接另一条对角线的两个接点。电路板左上角的接点接入直流电源，右下角的接点接入飞行车的发动装置。

Ha‘nyu发现因为某些元件的方向不小心发生了改变，电路板可能处于断路状态。她准备通过计算，旋转最少数量的元件，使电源与发动装置通过若干条短电缆相连。不过电路的规模实在太大了，Ha‘nyu不擅长编程，希望你能够帮她解决这个问题。

输入

输入文件包含多组测试数据。第一行包含一个整数T 表示测试数据的数目。
对于每组测试数据，第一行包含正整数 R 和C，表示电路板的行数和列数。
之后 R 行，每行C 个字符，字符是"/"和"\"中的一个，表示标准件的方向。
对于 100% 的数据，R,C≤500，T≤5。

输出

对于每组测试数据，在单独的一行输出一个正整数，表示所需的缩小旋转次数。
如果无论怎样都不能使得电源和发动机之间连通，输出 NO SOLUTION。

样例输入

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

样例输出

思路：二维数组不好建地图，所以用邻接表去建图，化二维地图用一维去存，利用权值为0的不可叠加性，用双端队列去BFS。

代码：

#include<bits/stdc++.h>

using namespace std;

#define maxn 1000

#define INF 0x3f3f3f3f

int n, m;

char tt[maxn][maxn];//存地图

int dis[maxn*maxn];

int ans = INF;

struct edge

{

    int e, w;//终点和路程

    edge(int _e, int _w)//构造函数初始化

    {

         e = _e;

         w = _w;

    }

};

vector<edge>Map[maxn*maxn];//建邻接表

void add_edge(int x, int y, int z)

{

    Map[x].push_back(edge(y, z));

}

int bfs(int s, int t)

{

    for (int i = 0; i < maxn*maxn; i++)dis[i] = INF;//双端队列BFS

    deque<int>p;

    p.push_back(s);

    dis[s] = 0;

    while (!p.empty())

    {

         int Now = p.back();

         p.pop_back();

         if (Now == t) return dis[Now];

         for (int i = Map[Now].size() - 1; i >= 0; i--)

         {

             int u = Map[Now][i].e, c = Map[Now][i].w;

             if (dis[u] > dis[Now] + c)

             {

                  dis[u] = dis[Now] + c;

                  if (c == 0)

                      p.push_back(u);//若边权为0放在后面

                  else

                      p.push_front(u);//若边权为1放在前面

             }

         }

    }

    return dis[t];



}

int main()

{

    int T;

    cin >> T;

    while (T--)

    {

         ans = INF;

         for (int i = 0; i <= maxn * maxn; i++)Map[i].clear();//邻接表清空

         cin >> n >> m;

         for (int i = 1; i <= n; i++)

         {

             for (int j = 1; j <= m; j++)

             {

                  cin >> tt[i][j];

             }

         }

         //zuo

         for (int i = 1; i <= n; i++)

         {

             for (int j = 1; j <= m; j++)

             {



                  add_edge((i - 1)*(m + 1) + j, i*(m + 1) + j - 1, tt[i][j] != '/');//将二维图转化为一维图

                  add_edge(i*(m + 1) + j - 1, (i - 1)*(m + 1) + j, tt[i][j] != '/');

                  add_edge((i - 1)*(m + 1) + j - 1, i*(m + 1) + j, tt[i][j] == '/');

                  add_edge(i*(m + 1) + j, (i - 1)*(m + 1) + j - 1, tt[i][j] == '/');



             }

         }

         ans = bfs(0, n*(m + 1) + m);

         if (ans == INF)cout << "NO SOLUTION" << endl;

         else cout << ans << endl;

    }

}