度小满第二题暴搜问题。

#include<bits/stdc++.h>
using namespace std;
int N,K;

int ans = 0xffffff;

void dfs(vector<vector<char> > &s,int sx,int sy,int sum,vector<vector<int> > &flag){ 
    if(sx == N-1 && sy == N-1){
        ans = min(ans,sum);
        return;
    }
   
    int dx[4] = {1,0,-1,0},dy[4] = {0,1,0,-1};
    
    for(int i = 0; i < 4;i++){
		int x = sx + dx[i];
        int y = sy + dy[i];
        if(x >= 0 && x < N && y >= 0 && y < N && flag[x][y] && s[x][y] != '1'){
            int t = sum;
            if(s[x][y] == '#'){
                sum += (K + 1);
            }
            else{
                sum += 1;
            }
            flag[x][y] = 0;
            dfs(s,x,y,sum,flag);
            flag[x][y] = 1;
            sum = t;
        }
    }
}

int main(){
    cin>>N>>K;
    vector<vector<char> > s(N,vector<char>(N,'0')); 
    for(int i = 0; i < N;i++){
        for(int j = 0; j < N;j++){
            cin>>s[i][j];
        }
    }
    vector<vector<int> > flag(N,vector<int>(N,1));
    dfs(s,0,0,0,flag);
    if(ans == 0xffffff){
    	cout<<"No Solution"<<endl;
	}else{
		cout<<ans<<endl;
	}
    return 0;
}
奈何,我一个初始化写错了没有ac,难受。#笔试题目##度小满#
全部评论

相关推荐

2 收藏 评论
分享
牛客网
牛客企业服务