AOJ0245 タイムセール

解法

---

幅優先でやった。
「これ絶対いいやろ(確信)」と思って提出したソースが4回くらい違って何度も絶望した問題だった。
大きな原因としては売り切れる時刻までを買える時刻に含んでいたこと。察せない。
以下ソース42行目。>=を>にずっとしていた。さらに察せない。
気づけてよかった。

後から他の人の解法見ると深さで実装してて実装量少ないし良いなあとは思った。
探索≒bfsに自分の頭の中で脳内変換されてしまう。早いから(ry(言い訳)

ソース

---

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<cctype>
using namespace std;
typedef pair< int , int > Pt;
typedef pair< pair<int , Pt > , Pt > P; // Pt(cost,bit) , Pt(y,x)
#define fr first
#define sc second
#define INF ( 1 << 30 )
const int dx[] = { 0, 1, -1, 0}, dy[] = { 1, 0, 0, -1};
struct edge{
  int prime,st,ed;
  edge(){};
  edge(int prime,int st,int ed):prime(prime),st(st),ed(ed){}
};
edge info[11];
int x, y;
char mas[21][21];
bool no_over(int ny,int nx){
  return ny >= 0 && ny < y && nx >= 0 && nx < x;
}
int bfs(Pt& start){
  int ret = 0;
  bool used[21][21][1<<11];
  fill_n(used[0][0],20*20*(1<<11),false);
  queue< P >que;
  que.push(P(make_pair(0,Pt((1<<10)-1,0)),start));
  used[start.fr][start.sc][(1<<10)-1] = true;
  while(!que.empty()){
    P p = que.front();
    que.pop();
    for(int i = 0 ; i < 4 ; i++ ){
      int ny = p.sc.fr + dy[i], nx = p.sc.sc + dx[i];
      if(!no_over(ny,nx)) continue;
      if(isdigit(mas[ny][nx])){
        edge e = info[mas[ny][nx]-'0'];
        int no = mas[ny][nx] - '0';
        ny = p.sc.fr, nx = p.sc.sc;
        if( !(p.fr.sc.fr & (1 << no)) || p.fr.fr >= e.ed) continue;
        if(p.fr.fr >= e.st){
          ret = max(ret,p.fr.sc.sc + e.prime);
          if(used[ny][nx][p.fr.sc.fr&~(1<<no)]++) continue;
          que.push(P(make_pair(p.fr.fr,Pt(p.fr.sc.fr&~(1<<no),p.fr.sc.sc + e.prime)),Pt(ny,nx)));
        }else que.push(P(make_pair(e.st,Pt(p.fr.sc.fr,p.fr.sc.sc)),Pt(ny,nx)));
      }else{
        if(used[ny][nx][p.fr.sc.fr]++) continue;
        que.push(P(make_pair(p.fr.fr+1,Pt(p.fr.sc.fr,p.fr.sc.sc)),Pt(ny,nx)));
      }
    }
  }
  return ret;
}
 
int main(){
  while(cin >> x >> y , x){
    Pt st;
    for(int i = 0 ; i < y ; i++ ){
      for(int j = 0 ; j < x ; j++ ){
        cin >> mas[i][j];
        if(mas[i][j] == 'P') st = Pt(i,j);
      }
    }
    int n;
    cin >> n;
    for(int i = 0 ; i < n ; i++ ){
      int g,d,s,e;
      cin >> g >> d >> s >> e;
      info[g] = edge(d,s,e);
    }
    cout << bfs(st) << endl;
  }
}