ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

AOJ 0245 Time Sale

問題文はこちら
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0245


・概要
タイムセールが行われます。 何種類かの商品がタイムセールで売られるのですが、タイムセールをする時間がそれぞれ異なります。
店内の見取り図と買い物をする人の初期位置、タイムセール情報が与えられたとき、とることのできた商品の値引き額の合計の最大値を求める問題です。

問題文見たほうが分かりやすいと思います。


・解法
BFS(幅優先探索)で解くことができます。

キューには、現在値(x、y)、現在の時間、値引き額の合計、まだ訪れていない商品(ビットで表現)をつっこんでやります。
ビットで持たせることが重要です!!


ソースコード

#include<iostream>
#include<algorithm>
#include<map>
#include<queue>
#include<cstring>
using namespace std;

#define rep(i,n) for(int i = 0 ; i < (int)(n) ; i++)

static const int INF = (1 << 29);
static const int dx[] = {1,-1,0,0};
static const int dy[] = {0,0,1,-1};

struct State{
   int x,y,t,sum,unvisit;
   State(int x, int y, int t, int s, int v):x(x),y(y),t(t),sum(s),unvisit(v){};
};
					   
struct Goods{
   int price,s,e;
   Goods(){}
   Goods(int p, int s, int e):price(p),s(s),e(e){};
};

int h,w,n;
int sx,sy;
int G[20][20];
Goods goods[10];
bool visited[20][20][(1 << 10)][101];

int bfs(){
   memset(visited,false,sizeof(visited));
   int ans = 0;
   queue<State> q;
   q.push(State(sx, sy, 0, 0, (1<<10)-1));

   while(!q.empty()){
      State s = q.front();
      q.pop();
      
      if(s.t > 100)continue;      
      if(visited[s.x][s.y][s.unvisit][s.t])continue;
      visited[s.x][s.y][s.unvisit][s.t] = true;
      ans = max(ans, s.sum);
      
      rep(k,4){
	 int nx = s.x + dx[k];
	 int ny = s.y + dy[k];
	 
	 if(0<=nx&&nx<h && 0<=ny&&ny<w && G[nx][ny]!=-1){
	    int num = G[nx][ny];
	    if((s.unvisit >> num) & 1){
	       if(goods[num].s <= s.t && s.t < goods[num].e){
		  s.sum += goods[num].price;
		  s.unvisit = s.unvisit & ~(1 << num);
	       }
	    }
	 }
      }

      rep(k,4){
	 int nx = s.x + dx[k];
	 int ny = s.y + dy[k];
	 
	 if(0<=nx&&nx<h && 0<=ny&&ny<w && G[nx][ny]==-1){
	    q.push(State(nx, ny, s.t+1, s.sum, s.unvisit));
	 }
      }
   }
   return ans;
}

void input(){
   rep(i,h){
      rep(j,w){
	 char c;
	 cin >> c;
	 if(c=='P'){
	    sx = i;
	    sy = j;
	    G[i][j] = -1;
	 }
	 else if(c=='.')G[i][j] = -1;
	 else G[i][j] = (int)(c - '0');
      }
   }
   
   cin >> n;
   rep(i,n){
      int g,d,s,e;
      cin >> g >> d >> s >> e;
      goods[g] = Goods(d,s,e);
   }
}

int main(){
   while(cin >> w >> h){
      if(w==0 && h==0)break;
      input();
      cout << bfs() << endl;
   }
   return 0;
}