Untitled
unknown
plain_text
20 days ago
2.7 kB
1
Indexable
Never
#include <iostream> using namespace std; class Queue { private: int Data[300]; public: int front, rear; Queue(); void enQueue(int value); void reset(); int deQueue(); bool is_Empty(); }; Queue::Queue(){ front=rear=-1; } void Queue::reset(){ front=rear=-1; } void Queue::enQueue(int value){ Data[++rear]=value; } int Queue::deQueue(){ return Data[++front]; } bool Queue::is_Empty(){ return front==rear; } Queue rFQueue, cFQueue; int N,M,K,SR,SC, Max, cntD, nextStep; int D[15][15], Lake[15][15], Exit[15][15], visitF[15][15], visitH[15][15]; int cntFire, cntLake, cntExit; int dx[]={0,0,-1,1}, dy[]={-1,1,0,0}; int nr, nc, cr, cc; void EtFire(){ while (rFQueue.is_Empty()==false){ cr=rFQueue.deQueue(); cc=cFQueue.deQueue(); for (int idx=0; idx<4; idx++){ nr=cr+dx[idx]; nc=cc+dy[idx]; if (nr>=0 && nr<N && nc>=0 && nc<M && visitF[nr][nc]==1000000 && Lake[nr][nc]==0) { rFQueue.enQueue(nr); cFQueue.enQueue(nc); visitF[nr][nc]=visitF[cr][cc]+1; } } } } void backtrack(int r, int c, int cntStep){ if (Exit[r][c]==1){ if (Max<cntD) Max=cntD; } for (int i=0; i<4; i++){ int Nr = r+dx[i]; int Nc = c+dy[i]; if (Nr>=0 && Nr<N && Nc>=0 && Nc<M && visitH[Nr][Nc]==false) { if (Lake[Nr][Nc]==0){ nextStep=cntStep+1; if (nextStep<visitF[Nr][Nc]) { cntD += D[Nr][Nc]; visitH[Nr][Nc]=true; backtrack(Nr,Nc,nextStep); cntD -= D[Nr][Nc]; visitH[Nr][Nc]=false; } } else { nextStep=cntStep+2; cntD += D[Nr][Nc]; visitH[Nr][Nc]=true; backtrack(Nr,Nc,nextStep); cntD -= D[Nr][Nc]; visitH[Nr][Nc]=false; } } } } int main(){ freopen("input.txt", "r", stdin); int T, x, y ; cin>>T; for (int tc=1; tc<=T; tc++){ rFQueue.reset(); cFQueue.reset(); cin>>N>>M>>SR>>SC; SR--; SC--; for (int i=0; i<N; i++){ for (int j=0; j<M; j++){ Lake[i][j]=0; Exit[i][j]=0; visitF[i][j]=1000000; visitH[i][j]=0; } } visitH[SR][SC]=1; cin>>cntFire; for (int i=0; i<cntFire; i++){ cin>>x; cin>>y; visitF[x-1][y-1]=0; rFQueue.enQueue(x-1); cFQueue.enQueue(y-1); } cin>>cntLake; for (int i=0; i<cntLake; i++){ cin>>x; cin>>y; Lake[x-1][y-1]=1; } cin>>cntExit; for (int i=0; i<cntExit; i++){ cin>>x; cin>>y; Exit[x-1][y-1]=1; } for (int i=0; i<N; i++){ for (int j=0; j<M; j++){ cin>>D[i][j]; } } EtFire(); cntD=D[SR][SC]; Max=-1; backtrack(SR,SC,0); cout<<"Case #"<<tc<<endl<<Max<<endl; } return 0; }
Leave a Comment