1019.cpp

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

#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
int p[4][2]={0,1,1,0,0,-1,-1,0};
class item{
public:
	int si,sj,i,j;
	item(int a,int b,int c,int d){si=a;sj=b;i=c;j=d;}
};
class act{
public:
	int f,t,d;
	act(int a,int b){f=a;t=b;}
};
int main(){
    //ifstream cin("in.txt");
	int testcase,n,m,l,i,j,k;
	char c;
	cin>>testcase;
    for(l=0;l<testcase;l++){
       cin>>m>>n;
	   vector<int> _temp(n);
	   vector<vector<int> > map(m,_temp);
	   vector<item> last,now;
	   vector<act> vecact;
	   for(i=0;i<m;i++)
		   for(j=0;j<n;j++){
               cin>>map[i][j];
			   if(map[i][j]==0) last.push_back(item(i,j,i,j)); 
		   }
	   while(cin>>i>>j&&!(i==0&&j==0)){
           vecact.push_back(act(i,j));
		   cin>>c;
		   if(c=='R') vecact.back().d=0;
		   else if(c=='D') vecact.back().d=1;
		   else if(c=='L') vecact.back().d=2;
		   else vecact.back().d=3;
	   }
	   //cout<<vecact.size()<<endl;
	   for(k=0;k<vecact.size();k++){
		   //cout<<vecact[k].f<<" "<<vecact[k].t<<" "<<vecact[k].d<<endl;
           //cout<<k<<" "<<last.size()<<endl;
		   if(last.size()==0) break;
		   for(i=0;i<last.size();i++){
			   for(j=1;j<=vecact[k].t;j++){
                   int ii=last[i].i+j*p[vecact[k].d][0],jj=last[i].j+j*p[vecact[k].d][1];
				   //cout<<"ii jj"<<" "<<ii<<" "<<jj<<endl;
				   if(ii>=0&&jj>=0&&ii<m&&jj<n&&map[ii][jj]==0){
                       if(j>=vecact[k].f) {
						   //cout<<j<<" "<<vecact[k].f<<" "<<ii<<endl;
						   //cout<<k<<" "<<last[i].si<<" "<<last[i].sj<<" "<<ii<<" "<<jj<<endl;
						   now.push_back(item(last[i].si,last[i].sj,ii,jj));/* cout<<"asd"<<endl;*/
					   }
				   }
				   else break;
			   }//for j
		   }//for i
		   last=now; now.clear();
	   }
	   //cout<<last.size()<<endl;
	   /*for(i=0;i<last.size();i++)
		   cout<<last[i].si<<" "<<last[i].sj<<endl;*/
	   j=0;
	   vector<int> temptemp(n,0);
	   vector<vector<int> > cmp(m,temptemp);
	   for(i=0;i<last.size();i++){
		   if(cmp[last[i].si][last[i].sj]==0){
              j+=1;
			  cmp[last[i].si][last[i].sj]=1;
		   }
	   }
	   cout<<j<<endl;
	}
}