【01BFS】# P4667 [BalticOI 2011] Switch the Lamp On 電路維修 (Day1)|普及+

本文涉及知識點

C++BFS算法

題目描述

Casper is designing an electronic circuit on a $\times M$ rectangular grid plate. There are $\times M$ square tiles that are aligned to the grid on the plate. Two (out of four) opposite corners of each tile are connected by a wire.

A power source is connected to the top left corner of the plate. A lamp is connected to the bottom right corner of the plate. The lamp is on only if there is a path of wires connecting power source to lamp. In order to switch the lamp on, any number of tiles can be turned by 90° (in both directions).
在這里插入圖片描述

在這里插入圖片描述

In the picture above the lamp is off. If any one of the tiles in the second column from the right is turned by 90° , power source and lamp get connected, and the lamp is on.

Write a program to find out the minimal number of tiles that have to be turned by 90° to switch the lamp on.

輸入格式

The first line of input contains two integer numbers $N$ and $M$ , the dimensions of the plate. In each of the following $N$ lines there are $M$ symbols – either \ or / – which indicate the direction of the wire connecting the opposite vertices of the corresponding tile.

輸出格式

There must be exactly one line of output. If it is possible to switch the lamp on, this line must contain only one integer number: the minimal number of tiles that have to be turned to switch on the lamp. If it is not possible, output the string: NO SOLUTION

輸入輸出樣例 #1

輸入 #1

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

輸出 #1

說明/提示

對于 $40\%$ 的數據， $\le N \le 4$ ， $\le M \le 5$ 。

對于所有數據， $\le N,M \le 500$ 。

BFS 雙向隊列

一，本題是點圖，不是單格圖。故：r $\in$ [0,N],c $\in$ [0,M]。
二，本題能否保證每個點都只訪問一次？vis記錄最少改變次數，改變次數變少，才需要重新處理當前點的后續。因為是01BFS，所以可以保證所有節點只訪問一次。
三，用雙向隊列，如果不改變入隊首，改變入隊尾。這樣優先處理不改變，可以提速。
時間復雜度：O（NM）
任意時刻：雙向隊列要么全部是x，要么前邊是x，后邊是x+1。
x入隊首，x+1入隊尾，扔保持這種狀態。故x處理完之前，不會處理x+1。

代碼

核心代碼

#include <iostream>
#include <sstream>
#include <vector>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<string>
#include<algorithm>
#include<functional>
#include<queue>
#include <stack>
#include<iomanip>
#include<numeric>
#include <math.h>
#include <climits>
#include<assert.h>
#include<cstring>
#include<list>#include <bitset>
using namespace std;template<class T1, class T2>
std::istream& operator >> (std::istream& in, pair<T1, T2>& pr) {in >> pr.first >> pr.second;return in;
}template<class T1, class T2, class T3 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3>& t) {in >> get<0>(t) >> get<1>(t) >> get<2>(t) ;return in;
}template<class T1, class T2, class T3, class T4 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3, T4>& t) {in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t);return in;
}template<class T = int>
vector<T> Read() {int n;scanf("%d", &n);vector<T> ret(n);for(int i=0;i < n ;i++) {cin >> ret[i];}return ret;
}template<class T = int>
vector<T> Read(int n) {vector<T> ret(n);for (int i = 0; i < n; i++) {cin >> ret[i];}return ret;
}template<int N = 12 * 1'000'000>
class COutBuff
{
public:COutBuff() {m_p = puffer;}template<class T>void write(T x) {int num[28], sp = 0;if (x < 0)*m_p++ = '-', x = -x;if (!x)*m_p++ = 48;while (x)num[++sp] = x % 10, x /= 10;while (sp)*m_p++ = num[sp--] + 48;}inline void write(char ch){*m_p++ = ch;}inline void ToFile() {fwrite(puffer, 1, m_p - puffer, stdout);}
private:char  puffer[N], * m_p;
};template<int N = 12 * 1'000'000>
class CInBuff
{
public:inline CInBuff() {fread(buffer, 1, N, stdin);}inline int Read() {int x(0), f(0);while (!isdigit(*S))f |= (*S++ == '-');while (isdigit(*S))x = (x << 1) + (x << 3) + (*S++ ^ 48);return f ? -x : x;}
private:char buffer[N], * S = buffer;
};template<class TSave, class TRecord >
class CRangUpdateLineTree
{
protected:virtual void OnQuery(const TSave& save, const int& iSaveLeft, const int& iSaveRight) = 0;virtual void OnUpdate(TSave& save, const int& iSaveLeft, const int& iSaveRight, const TRecord& update) = 0;virtual void OnUpdateParent(TSave& par, const TSave& left, const TSave& r, const int& iSaveLeft, const int& iSaveRight) = 0;virtual void OnUpdateRecord(TRecord& old, const TRecord& newRecord) = 0;
};template<class TSave, class TRecord >
class CVectorRangeUpdateLineTree : public CRangUpdateLineTree<TSave, TRecord>
{
public:CVectorRangeUpdateLineTree(int iEleSize, TSave tDefault, TRecord tRecordNull) :m_iEleSize(iEleSize), m_save(iEleSize * 4, tDefault), m_record(iEleSize * 4, tRecordNull) {m_recordNull = tRecordNull;}void Update(int iLeftIndex, int iRightIndex, TRecord value){Update(1, 0, m_iEleSize - 1, iLeftIndex, iRightIndex, value);}void Query(int leftIndex, int rightIndex) {Query(1, 0, m_iEleSize - 1, leftIndex, rightIndex);}//void Init() {//	Init(1, 0, m_iEleSize - 1);//}TSave QueryAll() {return m_save[1];}void swap(CVectorRangeUpdateLineTree<TSave, TRecord>& other) {m_save.swap(other.m_save);m_record.swap(other.m_record);std::swap(m_recordNull, other.m_recordNull);assert(m_iEleSize == other.m_iEleSize);}
protected://void Init(int iNodeNO, int iSaveLeft, int iSaveRight)//{//	if (iSaveLeft == iSaveRight) {//		this->OnInit(m_save[iNodeNO], iSaveLeft);//		return;//	}//	const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;//	Init(iNodeNO * 2, iSaveLeft, mid);//	Init(iNodeNO * 2 + 1, mid + 1, iSaveRight);//	this->OnUpdateParent(m_save[iNodeNO], m_save[iNodeNO * 2], m_save[iNodeNO * 2 + 1], iSaveLeft, iSaveRight);//}void Query(int iNodeNO, int iSaveLeft, int iSaveRight, int iQueryLeft, int iQueryRight) {if ((iSaveLeft >= iQueryLeft) && (iSaveRight <= iQueryRight)) {this->OnQuery(m_save[iNodeNO], iSaveLeft, iSaveRight);return;}if (iSaveLeft == iSaveRight) {//沒有子節點return;}Fresh(iNodeNO, iSaveLeft, iSaveRight);const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;if (mid >= iQueryLeft) {Query(iNodeNO * 2, iSaveLeft, mid, iQueryLeft, iQueryRight);}if (mid + 1 <= iQueryRight) {Query(iNodeNO * 2 + 1, mid + 1, iSaveRight, iQueryLeft, iQueryRight);}}void Update(int iNode, int iSaveLeft, int iSaveRight, int iOpeLeft, int iOpeRight, TRecord value){if ((iOpeLeft <= iSaveLeft) && (iOpeRight >= iSaveRight)){this->OnUpdate(m_save[iNode], iSaveLeft, iSaveRight, value);this->OnUpdateRecord(m_record[iNode], value);return;}if (iSaveLeft == iSaveRight) {return;//沒有子節點}Fresh(iNode, iSaveLeft, iSaveRight);const int iMid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;if (iMid >= iOpeLeft){Update(iNode * 2, iSaveLeft, iMid, iOpeLeft, iOpeRight, value);}if (iMid + 1 <= iOpeRight){Update(iNode * 2 + 1, iMid + 1, iSaveRight, iOpeLeft, iOpeRight, value);}// 如果有后代，至少兩個后代this->OnUpdateParent(m_save[iNode], m_save[iNode * 2], m_save[iNode * 2 + 1], iSaveLeft, iSaveRight);}void Fresh(int iNode, int iDataLeft, int iDataRight){if (m_recordNull == m_record[iNode]){return;}const int iMid = iDataLeft + (iDataRight - iDataLeft) / 2;Update(iNode * 2, iDataLeft, iMid, iDataLeft, iMid, m_record[iNode]);Update(iNode * 2 + 1, iMid + 1, iDataRight, iMid + 1, iDataRight, m_record[iNode]);m_record[iNode] = m_recordNull;}vector<TSave> m_save;vector<TRecord> m_record;TRecord m_recordNull;const int m_iEleSize;
};class C01BFSDis
{
public:C01BFSDis(vector<vector<int>>& vNeiB0, vector<vector<int>>& vNeiB1, int s){m_vDis.assign(vNeiB0.size(), -1);std::deque<std::pair<int, int>> que;que.emplace_back(s, 0);while (que.size()){auto it = que.front();const int cur = it.first;const int dis = it.second;que.pop_front();if (-1 != m_vDis[cur]){continue;}m_vDis[cur] = it.second;for (const auto next : vNeiB0[cur]){if (-1 != m_vDis[next]){continue;}que.emplace_front(next, dis);}for (const auto next : vNeiB1[cur]){if (-1 != m_vDis[next]){continue;}que.emplace_back(next, dis + 1);}}}
public:vector<int> m_vDis;
};class Solution {
public:int Ans(vector<string>& mat) {const int R = mat.size();const int C = mat[0].size();auto Mask = [&](int r, int c) {return (C + 1) * r + c;};const int iMC = (R + 1) * (C + 1);vector<vector<int>> neiBo0(iMC), neiBo1(iMC);for (int r = 0; r < R; r++) {for (int c = 0; c < C; c++) {const int mask1 = Mask(r, c);const int mask2 = Mask(r + 1, c + 1);const int mask3 = Mask(r + 1, c);const int mask4 = Mask(r, c + 1);if ('\\' == mat[r][c]) {neiBo0[mask1].emplace_back(mask2);neiBo0[mask2].emplace_back(mask1);neiBo1[mask3].emplace_back(mask4);neiBo1[mask4].emplace_back(mask3);}else {neiBo0[mask3].emplace_back(mask4);neiBo0[mask4].emplace_back(mask3);neiBo1[mask1].emplace_back(mask2);neiBo1[mask2].emplace_back(mask1);}}}C01BFSDis bfs(neiBo0, neiBo1, 0);return bfs.m_vDis.back();}};int main() {
#ifdef _DEBUGfreopen("a.in", "r", stdin);
#endif // DEBUG	int R, C;cin >> R >> C;vector<string> mat(R);for (int r = 0; r < R; r++) {cin >> mat[r];}auto res = Solution().Ans(mat);if (res < 0) {cout << "NO SOLUTION";}else {cout << res;}	
#ifdef _DEBUG		/*printf("T=%d,", T);*/Out(mat, "mat=");
#endif // DEBUG	return 0;
}

單元測試

vector<string> mat;TEST_METHOD(TestMethod11){mat = { {"\\/"} };auto res = Solution().Ans(mat);AssertEx(-1, res);}TEST_METHOD(TestMethod12){mat = { {"\\/\\"} };auto res = Solution().Ans(mat);AssertEx(0, res);}TEST_METHOD(TestMethod13){mat = { {"///"} };auto res = Solution().Ans(mat);AssertEx(2, res);}TEST_METHOD(TestMethod14){mat = { "\\\\/\\\\","\\\\///","/\\\\\\\\" };auto res = Solution().Ans(mat);AssertEx(1, res);}

擴展閱讀

我想對大家說的話
工作中遇到的問題，可以按類別查閱鄙人的算法文章，請點擊《算法與數據匯總》。
學習算法：按章節學習《喜缺全書算法冊》，大量的題目和測試用例，打包下載。重視操作
有效學習：明確的目標及時的反饋拉伸區（難度合適）專注
聞缺陷則喜(喜缺)是一個美好的愿望，早發現問題，早修改問題，給老板節約錢。
子墨子言之：事無終始，無務多業。也就是我們常說的專業的人做專業的事。
如果程序是一條龍，那算法就是他的是睛
失敗+反思=成功成功+反思=成功