AtCoder Grand Contest 043 A - Range Flip Find Route(路径DP)

题目传送门

题意:给H * W黑白矩阵,求从(1,1)走到(H,W)路径全为白的最小翻转次数(可对小矩形进行翻转–(黑变白)(白变黑))

与路径DP类似,只是加了个判断:如果当前状态为黑且上一个状态为白则加1,否则是一个连续黑格子序列只用修改一次不加1.举个例子:


一共有两个连续黑色序列,所以最少修改2次,具体细节看代码。

#include<bits/stdc++.h>
using namespace std;
string a[100];
int dp[100][100],h,w;
const int inf=0x3f3f3f3f;
int main(){
	cin>>h>>w;
	for(int i=0;i<h;i++) cin>>a[i];
	dp[0][0]=(a[0][0]=='#');
	for(int i=0;i<h;i++)
		for(int j=0;j<w;j++)
			if(i+j!=0)
			{
				dp[i][j]=inf;
				if(i>0) dp[i][j]=min(dp[i][j],dp[i-1][j]+(a[i][j]=='#'&&a[i-1][j]=='.'));
				if(j>0) dp[i][j]=min(dp[i][j],dp[i][j-1]+(a[i][j]=='#'&&a[i][j-1]=='.'));
			}
	cout<<dp[h-1][w-1]<<endl;
	return 0;
}