AtCoder Grand Contest 043--A - Range Flip Fin…

2020-03-22 16:00:53来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

AtCoder Grand Contest 043--A - Range Flip Find Route

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.cnblogs.com/blogxsc/p/12546865.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:c++中的异常处理

下一篇:GPLT-天梯赛-题解目录