1255.cpp

ZOJ 动态规划算法题目入门与提高 源代码

#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
int p[4][2]={0,1,1,0,0,-1,-1,0};
void dfs(vector<vector<char> > & vec,int i,int j,char c,int & f,int n){
	if(c=='W'&&j==n-1||c=='B'&&i==n-1) {f=0;return;}
	else{
            for(int k=0;k<4;k++){
               int ii=i+p[k][0],jj=j+p[k][1];
			   if(ii>=0&&jj>=0&&ii<n&&jj<n&&vec[ii][jj]==c){
                  vec[ii][jj]='U';
				  dfs(vec,ii,jj,c,f,n);
				  if(f==0) break;
			   }
			}
	}
}
int main(){
	//ifstream cin("in.txt");
    int f,i,j,k,n,l;
	while(cin>>n&&n){
       vector<char> vecc(n);
	   vector<vector<char> > vec(n,vecc),temp;
       for(i=0;i<n;i++) for(j=0;j<n;j++) cin>>vec[i][j];
	   f=1;
	   if(f=1){ //white can win?
		   for(i=0;i<n;i++){
			   if(vec[i][0]=='W'){ 
				 temp=vec;
				 temp[i][0]='U';
				 dfs(temp,i,0,'W',f,n);
			     if(f==0) break;
			   }
		   }
		   if(f==0) cout<<"White has a winning path.\n";
	   }
	   if(f==1){ //black can win?
           for(j=0;j<n;j++){
               if(vec[0][j]=='B'){
                 temp=vec;
				 temp[0][j]='U';
				 dfs(temp,0,j,'B',f,n);
                 if(f==0) break;
			   }
		   }
		   if(f==0) cout<<"Black has a winning path.\n";
	   }
	   if(f==1){  //white move one??
           vector<int> cmpcmp(n,0);
		   vector<vector<int> > veccmp(n,cmpcmp);
		   vector<int> begini,beginj,nowi,nowj;
		   for(i=0;i<n;i++){
			   if(vec[i][0]=='W'){
                   begini.push_back(i);
				   beginj.push_back(0);
				   veccmp[i][0]=1;
			   }
		   }
		   while(begini.size()){
               for(l=0;l<begini.size();l++){
                   for(k=0;k<4;k++){
                      i=begini[l]+p[k][0];j=beginj[l]+p[k][1];
					  if(i>=0&&j>=0&&j<n&&i<n&&(vec[i][j]=='W'||vec[i][j]=='U')&&veccmp[i][j]==0){
                          veccmp[i][j]=1;
						  if(vec[i][j]=='W'){
						     nowi.push_back(i); nowj.push_back(j);
						  }
						  if(vec[i][j]=='U'&&j==n-1){f=0;goto outer1;}
					  }
				   }
			   }
			   begini=nowi;beginj=nowj;
			   nowi.clear();nowj.clear();
		   }
		   //反过来
		   begini.clear();beginj.clear();nowi.clear();nowj.clear();
		   for(i=0;i<n;i++){
			   if(vec[i][n-1]=='W'){
                   begini.push_back(i);
				   beginj.push_back(n-1);
				   veccmp[i][n-1]=1;
			   }
		   }
		   while(begini.size()){
               for(l=0;l<begini.size();l++){
                   for(k=0;k<4;k++){
                      i=begini[l]+p[k][0];j=beginj[l]+p[k][1];
					  if(i>=0&&j>=0&&j<n&&i<n&&vec[i][j]=='W'&&veccmp[i][j]==0){
                          veccmp[i][j]=1;
						  nowi.push_back(i); nowj.push_back(j);
					  }
                      if(i>=0&&j>=0&&j<n&&i<n&&vec[i][j]=='U'){
                          if(veccmp[i][j]==1||j==0){f=0;goto outer1;}
						  else veccmp[i][j]=1;
					  }
				   }
			   }
			   begini=nowi;beginj=nowj;
			   nowi.clear();nowj.clear();
		   }
           outer1:
		   if(f==0) cout<<"White can win in one move.\n";
	   }
	   if(f==1){  //black move one??
           vector<int> cmpcmp(n,0);
		   vector<vector<int> > veccmp(n,cmpcmp);
		   vector<int> begini,beginj,nowi,nowj;
		   for(i=0;i<n;i++){
			   if(vec[0][i]=='B'){
                   begini.push_back(0);
				   beginj.push_back(i);
				   veccmp[0][i]=1;
			   }
		   }
		   while(begini.size()){
               for(l=0;l<begini.size();l++){
                   for(k=0;k<4;k++){
                      i=begini[l]+p[k][0];j=beginj[l]+p[k][1];
					  if(i>=0&&j>=0&&j<n&&i<n&&(vec[i][j]=='B'||vec[i][j]=='U')&&veccmp[i][j]==0){
                          veccmp[i][j]=1;
						  if(vec[i][j]=='B'){
						     nowi.push_back(i); nowj.push_back(j);
						  }
						  if(vec[i][j]=='U'&&i==n-1){f=0;goto outer2;}
					  }
				   }
			   }
			   begini=nowi;beginj=nowj;
			   nowi.clear();nowj.clear();
		   }
		   //反过来
		   begini.clear();beginj.clear();nowi.clear();nowj.clear();
		   for(i=0;i<n;i++){
			   if(vec[n-1][i]=='B'){
                   begini.push_back(n-1);
				   beginj.push_back(i);
				   veccmp[n-1][i]=1;
			   }
		   }
		   while(begini.size()){
               for(l=0;l<begini.size();l++){
                   for(k=0;k<4;k++){
                      i=begini[l]+p[k][0];j=beginj[l]+p[k][1];
					  if(i>=0&&j>=0&&j<n&&i<n&&vec[i][j]=='B'&&veccmp[i][j]==0){
                          veccmp[i][j]=1;
						  nowi.push_back(i); nowj.push_back(j);
					  }
                      if(i>=0&&j>=0&&j<n&&i<n&&vec[i][j]=='U'){
                          if(veccmp[i][j]==1||i==0){f=0;goto outer2;}
						  else veccmp[i][j]=1;
					  }
				   }
			   }
			   begini=nowi;beginj=nowj;
			   nowi.clear();nowj.clear();
		   }
           outer2:
		   if(f==0) cout<<"Black can win in one move.\n";
	   }
	   if(f==1) cout<<"There is no winning path.\n";
	}
	return 0;
}