本文主要是介绍ZOJ 2100 seed,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
挺简单的深搜题。。但是因为粗心,跑完一个test case后没有正确地更新field数组(开始时为求精简竟然在格子(i,j)为 false时不令field[i][j] = false,原因是我以为field[6][6]是全局变量,默认情况是初始化为false,所以想当然地以为如果格子(i,j)是false就不用多次一举。。可是我忘了每次运行一个test case后field会改的。。SB了
#include<iostream>
#include<fstream>
#include<cstring>
//#include "debug.h"
using namespace std;bool field[6][6]; //有石头则为true,无石头则为false
bool seed[6][6]; //已经播种则为true,否则为false
int n,m;
//bool res;
int k = 0; //已经播种的格子数
int total_seed = 0; //可播种格子总数
bool res;void dfs(int r,int c){if(res) return;if(k == total_seed){ res = true; return;}if(seed[r][c] == true || field[r][c] == true) return; //有石头或已播种seed[r][c] = true;++k;if(k == total_seed){ res = true; return;}if(r>0) dfs(r-1,c);if(r<n-1) dfs(r+1,c);if(c>0) dfs(r,c-1);if(c<m-1) dfs(r,c+1);--k;seed[r][c] = false;
}int main(){//ifstream cin("input.txt");while(cin>>n>>m){if(n==0 && m==0) break;char c;for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>c;if(c=='S') field[i][j] = true;else{ field[i][j] = false; ++total_seed;}}}if(field[0][0] == true) cout<<"NO"<<endl;dfs(0,0);if(res) cout<<"YES"<<endl;else cout<<"NO"<<endl;memset(seed,0,36);k = 0;total_seed = 0;res = false;}return 0;
}
这篇关于ZOJ 2100 seed的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!