collect more jewels(bfs+dfs).cpp

杭电acm解题报告2001---2099.

#include <cstdio>
#include <string>
#include <queue>
#include <algorithm>
using namespace std;

int t,w,h,l,m,all;
char mmap[60][60];
int value[15];
bool hash[55][55][15];
int path[15][15];
int dic[4][2] =
{ {1,0},{-1,0},{0,1},{0,-1} };
int mmax;
struct node {
    int x,y,t,f;
	
	bool isok() {
		if (x<0 || y<0 || x>=h || y >=w || mmap[x][y] == '*' || hash[x][y][f]) {
			return false;
		}
		return true;
	}
}pos[15];
queue<node> SQ;

void bfs()
{
    int i,j,ll;
    node now,next;
	
    while (!SQ.empty()) {
        ll = SQ.size();
        while (ll--) {
            now = SQ.front();
            SQ.pop();
            for (i=0;i<4;i++) {
                next = now;
                next.x += dic[i][0];
                next.y += dic[i][1];
                next.t ++;
				
                if (next.isok()) {
					hash[next.x][next.y][next.f] = true;
					SQ.push(next);
                    if (mmap[next.x][next.y] >= 'A' && mmap[next.x][next.y] <= 'L') {
						path[next.f][mmap[next.x][next.y] -'A'] = next.t;
						path[mmap[next.x][next.y] -'A'][next.f] = next.t;
						next.t = 0;
						next.f = mmap[next.x][next.y] -'A';
						hash[next.x][next.y][next.f] = true;
						SQ.push(next);
					}
                }
            }//for i
        }//while ll
    }
}

bool mark[15];
void dfs(int pos, int v, int t)
{
	int i,j;
	if (t > l || mmax == all) {
		return ;
	}
	if (path[pos][m+1] != -1 && path[pos][m+1]+t <= l && v > mmax) {
		mmax = v;
	}
	for (i=0;i<m;i++) {
		if (!mark[i] && path[pos][i] != -1) {
			mark[i] = true;
			dfs(i, v+value[i], t+path[pos][i]);
			mark[i] = false;
		}
	}
}

int main()
{
    int i,j,k;
    
    scanf("%d",&t);
    for (i=1;i<=t;i++) {
		if (i>=2) {
			printf("\n");
		}
        scanf("%d %d %d %d",&w,&h,&l,&m);
        printf("Case %d:\n",i);
		all = 0;
		value[m] = value[m+1] = 0;
        for (j=0;j<m;j++) {
            scanf("%d",&value[j]);
			all += value[j];
        }
        getchar();
		memset(pos,0,sizeof(pos));
        for (j=0;j<h;j++) {
            gets(mmap[j]);
            for (k=0;k<w;k++) {
                if (mmap[j][k] == '@') {
                    pos[m].x = j;
                    pos[m].y = k;
					pos[m].f = m;
                    mmap[j][k] = 'A'+m;
                }
                else if (mmap[j][k] == '<') {
                    pos[m+1].x = j;
                    pos[m+1].y = k;
					pos[m+1].f = m+1;
                    mmap[j][k] = 'A'+m+1;
                }
				else if(mmap[j][k] >='A' && mmap[j][k] <= 'J') {
					pos[mmap[j][k]-'A'].x = j;
					pos[mmap[j][k]-'A'].y = k;
					pos[mmap[j][k]-'A'].f = mmap[j][k]-'A';
				}
            }
        }
		mmax = -1;
		memset(path, -1,sizeof(path));
		memset(hash, 0,sizeof(hash));
		int ll = SQ.size();
		while (ll--) {
			SQ.pop();
		}
		hash[pos[m].x][pos[m].y][pos[m].f] = true;
		SQ.push(pos[m]);
		bfs();
		
		
		if (path[m][m+1] > l || path[m][m+1] == -1) {
			printf("Impossible\n");
			continue ;
		}
		memset(mark,0,sizeof(mark));
		mark[m] = true;
		dfs(m,0,0);
        if (mmax == -1) {
            printf("Impossible\n");
        }
        else {
            printf("The best score is %d.\n",mmax);
        }
    }
}