1479.cpp

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

#include<vector>
#include<iostream>
#include<fstream>
using namespace std;
int p[8][2]={0,1,1,0,-1,0,0,-1,1,1,-1,-1,1,-1,-1,1};
void dfs(vector<vector<int> > & map,vector<vector<int> > & walk,int m,int n,int ii,int jj){
    int i,j,k;
	for(k=0;k<8;k++){
       i=ii+p[k][0];j=jj+p[k][1];
	   if(i>=0&&j>=0&&i<m&&j<n&&walk[i][j]==0&&map[i][j]==0){
           walk[i][j]=1;
		   dfs(map,walk,m,n,i,j);
	   }
	}
}
void buildmap(vector<vector<int> > & map,vector<int> & veci,vector<int> & vecj,vector<char> & vecc,const int m,const int n,vector<int> & li,vector<int> & lj){
	for(int i=0;i<vecc.size();i++){
        int pi=veci[i],pj=vecj[i];
		switch (vecc[i]){
		case 'u':{
             pi-=1;
			 while(pi>=0&&map[pi][pj]!=1){
		         map[pi][pj]=2;
				 li.push_back(pi);lj.push_back(pj);
				 pi-=1;
			 }
			 break;
		}
		case 'd':{
             pi+=1;
			 while(pi<m&&map[pi][pj]!=1){
		         map[pi][pj]=2;
				 li.push_back(pi);lj.push_back(pj);
				 pi+=1;
			 }
			 break;
		}
		case 'l':{
             pj-=1;
			 while(pj>=0&&map[pi][pj]!=1){
		         map[pi][pj]=2;
				 li.push_back(pi);lj.push_back(pj);
				 pj-=1;
			 }
			 break;
		}
		case 'r':{
             pj+=1;
			 while(pj<n&&map[pi][pj]!=1){
		         map[pi][pj]=2;
				 li.push_back(pi);lj.push_back(pj);
				 pj+=1;
			 }
			 break;
		}
		}
	}
}
bool can(vector<vector<int> > & map,vector<vector<int> > & walk,int i,int j,int m,int n){
    for(int k=0;k<8;k++){
       int ii=i+p[k][0],jj=j+p[k][1];
	   if(ii>=0&&jj>=0&&ii<m&&jj<n&&walk[ii][jj]==1&&map[ii][jj]==0)
		   return 1;
	}
	return 0;
}
int main(){
  //ifstream cin("in.txt");
  int f,m,n,i,j,x1,x2,y1,y2,l,a,b,d;
  char c;
  while(cin>>m>>n){
     vector<int> vectemp(n,0),veci,vecj,li,lj;
	 vector<char> vecc;
	 vector<vector<int> > map(m,vectemp),walk(m,vectemp);
	 cin>>x1>>y1>>x2>>y2>>l;
	 x1-=1;y1-=1;x2-=1;y2-=1;
	 //cout<<x1<<" "<<y1<<" "<<x2<<" "<<y2<<endl;
	 for(i=0;i<l;i++){
         cin>>a>>b>>c;
		 a-=1;b-=1;
		 if(c!='B') {
            veci.push_back(a); vecj.push_back(b); vecc.push_back(c);
		 }
		 map[a][b]=1;
	 }
	 if(x1==x2&&y1==y2) {cout<<"0\n"; continue;}
	 buildmap(map,veci,vecj,vecc,m,n,li,lj);
/*	 for(i=0;i<m;i++){
			 for(j=0;j<n;j++)
				 cout<<map[i][j];
			 cout<<endl;
	 }
	 cout<<endl;*/
	 veci.clear();vecj.clear();
	 veci.push_back(x1);vecj.push_back(y1);f=0;d=0;
	 while(veci.size()){
         for(l=0;l<veci.size();l++){
			      //cout<<veci[l]<<" "<<vecj[l]<<endl;
                  walk[veci[l]][vecj[l]]=1;
				  dfs(map,walk,m,n,veci[l],vecj[l]);
		 }
		/*for(i=0;i<m;i++){
			 for(j=0;j<n;j++)
				 cout<<walk[i][j];
			 cout<<endl;
		 }
		 cout<<endl;*/
		 if(walk[x2][y2]==1){cout<<d<<endl;f=1;break;}
		 veci.clear();
		 vecj.clear();
		 for(i=0;i<li.size();i++){
             if(can(map,walk,li[i],lj[i],m,n)){
                  veci.push_back(li[i]);
				  vecj.push_back(lj[i]);
				  li.erase(&li[i]);
				  lj.erase(&lj[i]);
				  i-=1;
			 }
		 }
		 d++;
	 }
	 if(f==0) cout<<"-1\n";
  }
  return 0;
}