【題目描述】

譯自 BalticOI 2011 Day1 T3「Switch the Lamp On」

有一種正方形的電路元件，在它的兩組相對頂點(diǎn)中，有一組會(huì)用導(dǎo)線連接起來，另一組則不會(huì)。

有 N×M 個(gè)這樣的元件，你想將其排列成 N 行 M 列放在電路板上。電路板的左上角連接電源，右下角連接燈泡。

試求：至少要旋轉(zhuǎn)多少個(gè)正方形元件才能讓電源與燈泡連通，若無解則輸出 NO SOLUTION。

【輸入】

有多組測試數(shù)據(jù)。

第一行為測試數(shù)據(jù)組數(shù)，以下每組測試數(shù)據(jù)描述為：

第一行有兩個(gè)整數(shù) N 和 M。

在接下來的 N 行中，每行有 M 個(gè)字符。每個(gè)字符均為 "\" 或 "/"，表示正方形元件上導(dǎo)線的連接方向。

【輸出】

每組測試數(shù)據(jù)輸出描述：

輸出共一行，若有解則輸出一個(gè)整數(shù)，表示至少要旋轉(zhuǎn)多少個(gè)正方形元件才能讓電源與燈泡連通；若無解則輸出 NO SOLUTION。

【輸入樣例】

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

【輸出樣例】

1

思路：

問題的關(guān)鍵在于思維的轉(zhuǎn)換，首先，由于從左上到右下走的是對角線，因此，僅當(dāng) (n+m)%2==1 時(shí)無解，其他情況一定有解

首先進(jìn)行建圖，將格子的字符轉(zhuǎn)為數(shù)字，即將 \ 轉(zhuǎn)為 0，將 / 轉(zhuǎn)為 1

然后考慮對角線格子的情況，無非以下四種：\\、\/、//、/\，同時(shí)，將這四種情況也轉(zhuǎn)為數(shù)字的形式存儲(chǔ)，相應(yīng)的，行走的花費(fèi)就為 0、1、0、1

再考慮所走的方向：左下、左上、右上、右下

此時(shí)，我們對圖進(jìn)行 BFS 搜索，考慮到兩種狀態(tài)：有花費(fèi)、無花費(fèi)，由于要使得花費(fèi)最低，因此每次從隊(duì)首出隊(duì)時(shí)，我們要選一個(gè)無花費(fèi)的元素出隊(duì)，故而可利用雙端隊(duì)列 deque 進(jìn)行優(yōu)化：當(dāng)有花費(fèi)時(shí)，從隊(duì)尾入隊(duì)，當(dāng)無花費(fèi)時(shí)，從隊(duì)首入隊(duì)，從而保證隊(duì)列的兩端性與單調(diào)性

此時(shí)只剩下一個(gè)問題，就是最小花費(fèi)的問題，即什么情況下才能將元素入隊(duì)，我們可以借助一個(gè)數(shù)組，存儲(chǔ)之前的花費(fèi)，當(dāng)某一步的花費(fèi)較之前的花費(fèi)縮小時(shí)，即將元素入隊(duì)

【源程序】

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #include<bitset> #define PI acos(-1.0) #define INF 0x3f3f3f3f #define LL long long #define Pair pair<int,int> LL quickPow(LL a,LL b){ LL res=1; while(b){if(b&1)res*=a; a*=a; b>>=1;} return res; } LL multMod(LL a,LL b,LL mod){ a%=mod; b%=mod; LL res=0; while(b){if(b&1)res=(res+a)%mod; a=(a<<=1)%mod; b>>=1; } return res%mod;} LL quickMultPowMod(LL a, LL b,LL mod){ LL res=1,k=a; while(b){if((b&1))res=multMod(res,k,mod)%mod; k=multMod(k,k,mod)%mod; b>>=1;} return res%mod;} LL quickPowMod(LL a,LL b,LL mod){ LL res=1; while(b){if(b&1)res=(a*res)%mod; a=(a*a)%mod; b>>=1; } return res; } LL getInv(LL a,LL mod){ return quickPowMod(a,mod-2,mod); } LL GCD(LL x,LL y){ return !y?x:GCD(y,x%y); } LL LCM(LL x,LL y){ return x/GCD(x,y)*y; } const double EPS = 1E-6; const int MOD = 1000000000+7; const int N = 1000+5; const int dx[] = {0,0,-1,1,1,-1,1,1}; const int dy[] = {1,-1,0,0,-1,1,-1,1}; using namespace std;struct Node {int x, y;int step;Node() {}Node(int x, int y, int step) : x(x), y(y), step(step) {} }; int n, m; int G[N][N]; //將格子的字符轉(zhuǎn)為數(shù)字 0:\ 1:/ int dirG[4][2] = {{0, 0}, {0, 1}, {1, 1}, {1, 0}}; /* 對角線格子的情況:\\,\/,//,/\ */ int disG[4] = {0, 1, 0, 1}; //對角線格子相應(yīng)的狀態(tài)下是否能走 int dir[4][2] = {{-1, -1}, {-1, 1}, {1, 1}, {1, -1}}; //走對角線的方向:左下,左上,右上,右下 int dis[N][N]; bool vis[N][N];void BFS() {deque<Node> Q;memset(vis, 0, sizeof(vis));memset(dis, INF, sizeof(dis));Q.push_front((Node){0, 0, 0});while (!Q.empty()) {Node node = Q.front();Q.pop_front();int x = node.x, y = node.y;int step = node.step;if (vis[x][y])continue;vis[x][y] = true;if (x == n && y == m) {printf("%d\n", step);return;}for (int i = 0; i < 4; i++) {int gx = x + dirG[i][0];int gy = y + dirG[i][1];if (gx < 0 || gy < 0 || gx > n || gy > m)continue;int nx = x + dir[i][0];int ny = y + dir[i][1];if (nx < 0 || ny < 0 || nx > n || ny > m)continue;if (dis[nx][ny] == INF) {if (G[gx][gy] != disG[i]) {Q.push_back(Node(nx, ny, step + 1));dis[nx][ny] = step + 1;} else {Q.push_front(Node(nx, ny, step));dis[nx][ny] = step;}} else if (G[gx][gy] == disG[i] && step < dis[nx][ny])Q.push_front(Node(nx, ny, step));}} } int main() {int t;scanf("%d", &t);while (t--) {scanf("%d%d", &n, &m);for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {char c = getchar();while (c != '\\' && c != '/')c = getchar();if (c == '\\')G[i][j] = 0;elseG[i][j] = 1;}}if ((n + m) % 2)printf("NO SOLUTION\n");elseBFS();}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的电路维修（信息学奥赛一本通-T1448）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。