dp动规 - 水质检测

题目题目分析有两行水质检测器每一行的长度皆为n现在的目的就是要让检测器之间联通求至少需要多添加几台水质检测器思路梳理错误思路看到有图的时候这道题我第一个思路想到了用BFS观察测试用例可以用BFS进行八个方向上、下、左、右和斜对角线斜对角线如果存在检测器就不进行标记只标记斜对角线不存在检测器的。但是这个想法会忽略了特殊情况如下图所示所以使用这个思路就很不合理特殊情况1. ## .特殊情况2# . . #. # # .正确思路对于每一列来说我们只有三种可能所以我们可以设置一个状态state控制状态的转移上面有检测器下面没有检测器设为 state 1上面没有检测器下面有检测器设为 state 2上下都有检测器设为 state 3我们用一个变量lst来记录遍历到第i列的时候我们上一列的出现检测器的位置然后中间出现了缺口没有检测器直接平铺一路检测器到第i列。重置状态。代码#includebits/stdc.h using namespace std; int main() { string s1,s2; cin s1 s2; // 状态 //1 代表上面有检测器下面没有 //2 代表下面有检测器上面没有 //3 代表上下都有检测器 int ans 0; int lst -1; int state -1;//状态 //第 i 列的检测器的状况 for(int i0;is1.size();i) { //没有出现检测器跳过 if(s1[i] . s1[i] .) { continue; } //上一次出现检测器的位置给他铺上检测器 if(lst ! -1) ans i - lst - 1; //上下都有检测器重置状态 if(s1[i] # s2[i] #) state 3; //上面有检测器下面没有检测器 else if(s1[i] # s2[i] .) { //state此时记录的是lst列检测器长什么样 //如果state 2上面没有下面有 if(state 2) { //给上面添一台检测器 ans; //更新状态 state 3; } //如果state ! 2上面有下面没有 else{ state 1; } } // s1[i] . s2[i] # else { // 上一列 // # // . if(state 1) { ans; state 3; }else { state 2; } } lst i; } cout ans; return 0; }