A - Range Flip Find Route
題意：本題就是給你一個矩陣，要你求出從（1，1）到（h，w）數量最少的黑色方塊
題解：在作這一題的時候我最初想到的是用DFS求出每一種可能的方式，比較出它們的最小值，結果TLE了，賽后補題，才懂得還可以用DP來做：這里我們定義一個二維陣列dp[h][w],其中dp[i][j]代表到達點（i，j）時候黑塊的最少塊數，同時代表這一塊需不需要翻轉，（題目說明，黑色塊要翻轉成白色塊），每次求出它們的最小值即可，
下面給出TLE的代碼：
#include<iostream> #include<cstring> #include<algorithm> #define ll long long using namespace std; int min_n=100*100+5; int sum=0;//存盤臨時答案 int h,w; char ptr[150][150]; int net[2][2]={{0,1},{1,0}}; bool check(int x,int y){ return (x<=h/*行*/)&&(y<=w/*列*/);//判斷合法 } void dfs(int x,int y){//全部遍歷，求最小的運算元 if(x==h&&y==w){//本次到達終點 min_n=min(min_n,sum);//取出最小值 return ;//結束本次的呼叫 } //尋找下一步 for(int i=0;i<2;i++){ int nx=x+net[i][0]; int ny=y+net[i][1];//找到下一步操作 //判斷下一步操作是否合法 if(check(nx,ny)){//如果合法 if(ptr[nx][ny]=='#'){//判斷下一個位置是 黑 還是 白 ，是黑 則 加一操作 sum++; } dfs(nx,ny); if(ptr[nx][ny]=='#'){ sum--; } } } } int main(){ cin>>h>>w; for(int i=1;i<=h;i++){ for(int j=1;j<=w;j++){ cin>>ptr[i][j]; } }//資料輸入完畢，下面開始處理資料 //先要判斷第一個是不是 if(ptr[1][1]=='#'){ sum++;//計數器加一操作 } dfs(1,1);//然后從一開始遍歷搜索 cout<<min_n<<endl; return 0; }
下面是AC的代碼：
#include<iostream> #include<cstring> #include<algorithm> #define ll long long using namespace std; int min_n=100*100+5; int sum=0;//存盤臨時答案 int h,w; char ptr[150][150]; int net[2][2]={{0,1},{1,0}}; bool check(int x,int y){ return (x<=h/*行*/)&&(y<=w/*列*/);//判斷合法 } void dfs(int x,int y){//全部遍歷，求最小的運算元 if(x==h&&y==w){//本次到達終點 min_n=min(min_n,sum);//取出最小值 return ;//結束本次的呼叫 } //尋找下一步 for(int i=0;i<2;i++){ int nx=x+net[i][0]; int ny=y+net[i][1];//找到下一步操作 //判斷下一步操作是否合法 if(check(nx,ny)){//如果合法 if(ptr[nx][ny]=='#'){//判斷下一個位置是 黑 還是 白 ，是黑 則 加一操作 sum++; } dfs(nx,ny); if(ptr[nx][ny]=='#'){ sum--; } } } } int main(){ cin>>h>>w; for(int i=1;i<=h;i++){ for(int j=1;j<=w;j++){ cin>>ptr[i][j]; } }//資料輸入完畢，下面開始處理資料 //先要判斷第一個是不是 if(ptr[1][1]=='#'){ sum++;//計數器加一操作 } dfs(1,1);//然后從一開始遍歷搜索 cout<<min_n<<endl; return 0; }
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/52968.html
標籤：C++
下一篇：c語言一道題