AOJ 0263 - Beat Panel (ビートパネル)

AOJ パソコン甲子園

問題概要

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0263
日本語なので省略。

解法

bitDPで解けました。
具体的には、

dp[何回目のビート音まで鳴ったか][ボタンの光り方] = 最大のスコア
dp[31][1<<16]

で解けました。
計算量としては、上記の見た目上の計算量に加えて、どの押し方を試して遷移するかが掛かります。
なので、

O(n * 2^16 * c)
... 定数省いたら O(nc)

となります。
制約の最大値であれば、6000万程度になりますね。
AOJのスペックなら普通に間に合う感じです。

コード

__builtin_popcount関数は結構便利です。
是非覚えておきたいところ。

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

int n, c;
int a[31], b[31];
int dp[31][1 << 16];

void solve(){
  memset(dp, -1, sizeof(dp));
  dp[0][0] = 0;

  for(int i = 0; i < n; i++){
    for(int j = 0; j < (1 << 16); j++){
      if(dp[i][j] == -1) continue;

      int nj = (j | a[i]);

      for(int k = 0; k < c; k++){
        int cal = (nj & b[k]);
        int pop = __builtin_popcount(cal);
        dp[i + 1][nj - cal] = max(dp[i + 1][nj - cal], dp[i][j] + pop);
      }
    }
  }

  int ans = 0;
  for(int i = 0; i < (1 << 16); i++){
    ans = max(ans, dp[n][i]);
  }
  cout << ans << endl;
}

int main(){
  while(cin >> n >> c, n){
    for(int i = 0; i < n; i++){
      a[i] = 0;
      for(int j = 0; j < 16; j++){
        int x;
        cin >> x;
        a[i] = (a[i] << 1) + x;
      }
    }

    for(int i = 0; i < c; i++){
      b[i] = 0;
      for(int j = 0; j < 16; j++){
        int x;
        cin >> x;
        b[i] = (b[i] << 1) + x;
      }
    }

    solve();
  }
}

会津合宿2013-Day1でコンテストを開きます！

ブログ更新するの久しぶりです。
最近ではあまりコンテストにも参加しておらず、すっかり引退ガチ勢となりましたが、会津合宿の1日目にコンテストを開催します。問題は割と易しめになったと思います。プロコン慣れしてる人は合宿のウォーミングアップのつもりで、初心者の方は勉強のつもりで、奮ってご参加ください。
コンテストはオープンだから、合宿に来てない人でも参加できるよっ！

コンテスト概要

日時2013年9月3日(火) 14:30-17:30
時間3時間
問題数6問 or 7問
難易度ACM/ICPC国内予選レベルを想定
チームチーム参加、個人参加、どちらでも結構です
問題ページAizu Online Judge
開始時間になったら、このページの一番上にコンテストページへのリンクが現れます。
備考蟻本持ってると解きやすいかも(?)

会津合宿の宣伝

UVa : 361 - Cops and Robbers

uva 幾何

問題概要

点集合C, R, Oが与えられる。
それぞれの集合には、点が最大200個含まれている。
Oの中の各点について、以下の3つのパターンの内どれになるか答えよ

  • この点が、Cの任意の3点により作られる三角形に包含される : safeと呼ぶ
  • この点が、Rの任意の3点により作られる三角形に包含される、かつsafeではない : robbedと呼ぶ
  • safeでもrobbedでもない場合 : neitherと呼ぶ

ただし、「点が三角形に包含される」とは、点が三角形の中に完全に入っている、もしくは点が三角形の辺上に乗っていることを意味する。

解法

さて、この問題で難しいところは「点集合の任意の3点から成る三角形に、ある点が含まれるかどうか」を計算することです。
一番単純な方法は、3点を三重ループで選んで点がその三角形に含まれるか判定する方法です。しかし、そうするとその三重ループに、さらにOの点を選ぶループがかかってくるので、O(200^4)になってしまいます。

もっと効率のいい方法で計算するには、凸包を使いましょう。
とりあえず、CとRの集合を凸包して凸多角形を作ります。
もし、この凸多角形の中に点が包含されていれば、「点集合の任意の3点から成る三角形に、点が含まれている」ということになります。

点集合の任意の３点から成る三角形というのは、必ず凸包の多角形に含まれているため、この計算法で判定することができます。

コーナーケース

以下のような感じのセットがあるっぽいので注意です。

0 2 1
    0 0  0 0
    0 0
0 3 1
    0 0  0 0  0 0
    0 0
2 3 1
    -5 0  5 0
    -5 0  5 0  5 0
    0 0
3 0 1
    0 0  10 0  -10 0
    20 0
0 0 0
Data set 1:
     Citizen at (0,0) is neither.

Data set 2:
     Citizen at (0,0) is robbed.

Data set 3:
     Citizen at (0,0) is robbed.

Data set 4:
     Citizen at (20,0) is neither.

プログラム

幾何のコードは、スパゲッティソースのコードを使用しています。

  • 凸包：O(n log n)
  • 凸多角形包含判定 : O(log n)
    • ただし、今回は点が辺上に乗っているかの判定を入れているので O(n) になります
#include <iostream>
#include <complex>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

#define EPS (1e-8)

typedef complex<double> P;

bool cmp(const P& a, const P& b){
  return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b);
}

double cross(const P& a, const P& b){
  return imag(conj(a) * b);
}

double dot(const P& a, const P& b){
  return real(conj(a) * b);
}

int ccw(P a, P b, P c) {
  b -= a;
  c -= a;
  if(cross(b, c) > 0)   return +1;
  if(cross(b, c) < 0)   return -1;
  if(dot(b, c) < 0)     return +2;
  if(norm(b) < norm(c)) return -2;
  return 0;
}

bool intersectSP(const P &a, const P &b, const P &p) {
  return abs(a - p) + abs(b - p) - abs(b - a) < EPS;
}

vector<P> convexHull(vector<P> ps){
  if(ps.size() < 3) return vector<P>();

  int sz = ps.size();
  int k = 0;
  vector<P> ch(2 * sz);

  sort(ps.begin(), ps.end(), cmp);

  for(int i = 0; i < sz; ch[k++] = ps[i++]){
    while(k >= 2 && ccw(ch[k - 2], ch[k - 1], ps[i]) <= 0){
      --k;
    }
  }
  for(int i = sz - 2, j = k + 1; i >= 0; ch[k++] = ps[i--]){
    while(k >= j && ccw(ch[k - 2], ch[k - 1], ps[i]) <= 0){
      --k;
    }
  }
  ch.resize(k - 1);

  vector<P> res;

  for(int i = 0; i < ch.size(); i++){
    bool flg = true;

    for(int j = 0; j < i; j++){
      if(ch[i] == ch[j]){
        flg = false;
        break;
      }
    }
    if(flg) res.push_back(ch[i]);
  }

  return res;
}

enum{OUT, ON, IN};

int convexContains(const vector<P> &pol, const P &p){
  const int n = pol.size();
  P g = (pol[0] + pol[n / 3] + pol[2 * n / 3]) / 3.0;
  int a = 0, b = n;

  while(a + 1 < b){
    int c = (a + b) / 2;
    if(cross(pol[a] - g, pol[c] - g) > 0){
      if(cross(pol[a] - g, p - g) > 0 && cross(pol[c] - g, p - g) < 0) b = c;
      else                                                             a = c;
    }
    else{
      if(cross(pol[a] - g, p - g) < 0 && cross(pol[c] - g, p - g) > 0) a = c;
      else                                                             b = c;
    }
  }
  b %= n;
  if(cross(pol[a] - p, pol[b] - p) < 0) return OUT;
  if(cross(pol[a] - p, pol[b] - p) > 0) return IN;

  for(int i = 0; i < pol.size(); i++){
    if(intersectSP(pol[i], pol[(i + 1) % pol.size()], p)){
      return ON;
    }
  }

  return OUT;
}

enum{NEITHER, SAFE, ROBBED};
string output[] = {"neither", "safe", "robbed"};

int c, r, o;
vector<P> C, R, O;
int kind[202];

void input(int n, vector<P> &v){
  P p;
  v.clear();

  for(int i = 0; i < n; i++){
    cin >> p.real() >> p.imag();
    v.push_back(p);
  }
}

int main(){
  for(int SET = 1; cin >> c >> r >> o, c || r || o; SET++){
    cout << "Data set " << SET << ":" << endl;

    input(c, C);
    input(r, R);
    input(o, O);

    C = convexHull(C);
    R = convexHull(R);

    memset(kind, NEITHER, sizeof(kind));

    for(int i = 0; i < o; i++){
      if(C.size() >= 1 && convexContains(C, O[i])){
        kind[i] = SAFE;
      }
    }

    for(int i = 0; i < o; i++){
      if(kind[i] != 0) continue;
      if(R.size() >= 1 && convexContains(R, O[i])){
        kind[i] = ROBBED;
      }
    }

    for(int i = 0; i < o; i++){
      cout << "     Citizen at ("
           << O[i].real() << "," << O[i].imag() << ") is "
           << output[kind[i]] << "." << endl;
    }

    cout << endl;
  }
}

UVa : 10364 - Square

uva DP

問題概要

M本(4以上20以下)の長さが様々な棒が与えられる。
これらM本の棒を使って正方形の4つの辺を作ることができるか答えよ。
棒は折ったり曲げたりしてはいけません。

解法

まず、正方形を絶対作れない場合を考えましょう。
棒の長さを全部足し合わせて、もしこの数字が4で割り切れなければ絶対に正方形を作れないですよね。もし、4で割り切れるならば、正方形になる可能性を持っています。
ここで、(棒の長さの合計 / 4)をlenと置きます。

さて、本当に正方形を作れるかどうかは、以下のDPで解けます。

dp[正方形の辺を何本作ったか(4)][どの棒を使用したか(2^M)] = このようなパターンを作れるか否か(0 or 1)

dp[4][2^M]が1になっていれば答えはyesです。

dp[i][j]からの遷移は以下のようになります。

  • jに含まれない新たな棒kを追加しようとするときのことを考える
    • kを追加することで、使用している棒の長さの合計が、lenの倍数になるならば
      • dp[i + 1][j | (1 << k)]が1になる
      • これは、lenの倍数になると、正方形の辺が１本増えるため
    • kを追加することで、使用している棒の長さの合計が、len*(i+1)より小さくなるならば
      • dp[i][j | (1 << k)]が1になる
    • もし、長さの合計がlen*(i+1)より大きくなってしまう場合は、棒を折り曲げたりしないと、正方形の辺を増やすことができないので無視

プログラム

#include <iostream>
#include <cstring>
using namespace std;

int n;
int t[21];
bool dp[5][1 << 21];

void solve(){
  int sum = 0;
  for(int i = 0; i < n; i++){
    sum += t[i];
  }

  if(sum % 4 != 0){
    cout << "no" << endl;
    return;
  }

  int len = sum / 4;
  int maxBit = 1 << n;

  memset(dp, 0, sizeof(dp));
  dp[0][0] = true;

  for(int i = 0; i < 4; i++){
    for(int j = 0; j < maxBit; j++){
      if(!dp[i][j]) continue;

      //使用している棒の長さの合計を求める
      sum = 0;
      for(int k = 0; k < n; k++){
        if(!(j & (1 << k))) continue;
        sum += t[k];
      }

      //現在構築中の辺の長さだけ取得
      sum -= i * len;

      for(int k = 0; k < n; k++){
        if(j & (1 << k)) continue;
        if(sum + t[k] == len){ //今構築中の辺が完成する場合
          dp[i + 1][j | (1 << k)] = true;
        }
        else if(sum + t[k] < len){ //今構築中の辺がまだ完成しない場合
          dp[i][j | (1 << k)] = true;
        }
      }
    }
  }

  cout << (dp[4][maxBit - 1] ? "yes" : "no") << endl;
}

int main(){
  int T;
  cin >> T;

  while(T--){
    cin >> n;
    for(int i = 0; i < n; i++){
      cin >> t[i];
    }
    solve();
  }
}

UVa : 10083 - Division

uva 数論

問題概要

int型の範囲に収まる正の数、t, a, bが入力される。
(t^a - 1)/(t^b -1)という式に関して、以下のどれに当てはまるか答えよ。

  • 答えが、100桁より短い整数になる
  • それ以外の答えになる（100桁以上であったり、小数であったりする場合）

解法

一つ一つ無駄なパターンをつぶしていきましょう。

  • tが1の場合
    • ゼロ除算が発生するため、答えは100桁より短い整数ではない
  • aとbが一致する場合
    • tがどんな値であれ、必ず答えは1になる
  • aをbで割り切れない
    • 答えが小数になる
  • ( (a-b) × log10(t) )が99より大きくなる
    • 答えが100桁以上の数になる
  • それ以外の場合
    • 答えは、100桁より短い整数になる
    • 単純にBigIntegerで計算していい
    • 何故なら、100桁より短くなる整数を満たすためには、aやbは大きくても100程度にしかならないから。普通にBigIntegerのpowとか使ってよし

プログラム

import java.util.*;
import java.math.BigInteger;

public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);

    while(sc.hasNextInt()){
      int t = sc.nextInt();
      int a = sc.nextInt();
      int b = sc.nextInt();

      System.out.printf("(%d^%d-1)/(%d^%d-1) ", t, a, t, b);

      // divide by 0
      if(t == 1){
        System.out.println("is not an integer with less than 100 digits.");
        continue;
      }

      // is not integer
      if(a % b != 0){
        System.out.println("is not an integer with less than 100 digits.");
        continue;
      }

      // is one
      if(a == b){
        System.out.println("1");
        continue;
      }

      // not less than 100 digits
      if((a - b) * Math.log10(t) > 99.0){
        System.out.println("is not an integer with less than 100 digits.");
        continue;
      }

      // calc
      BigInteger t_bi = new BigInteger(Integer.toString(t));
      BigInteger one = BigInteger.ONE;
      BigInteger calc =
        t_bi.pow(a).subtract(one).divide(t_bi.pow(b).subtract(one));

      if(calc.toString().length() >= 100){
        System.out.println("is not an integer with less than 100 digits.");
      }
      else{
        System.out.println(calc);
      }
    }
  }
}

Facebook Hacker Cup 2013 Qualification Round

参加記

Problem A : Beautiful strings

出現回数が多いアルファベットに対して、大きい数字を割り当てればいいだけです。

int main(){
  int T;
  cin >> T;

  string s;
  getline(cin, s);

  for(int CASE = 1; CASE <= T; CASE++){
    cout << "Case #" << CASE << ": ";

    getline(cin, s);

    int cnt[26];
    memset(cnt, 0, sizeof(cnt));

    for(int i = 0; i < s.length(); i++){
      if(!isalpha(s[i])) continue;
      cnt[tolower(s[i]) - 'a']++;
    }

    int ans = 0;

    sort(cnt, cnt + 26, greater<int>());

    for(int i = 0; i < 26; i++){
      if(cnt[i] == 0) break;
      ans += cnt[i] * (26 - i);
    }

    cout << ans << endl;
  }
}

Problem B : Balanced Smileys

DPで解きました。
dp[何文字目][カッコを何個開いた状態か] = true or false (このパターンがあるかないか)
文字数がnとしたとき、dp[n][0]がtrueならば、閉じカッコにより開きカッコが全て閉じられて、カッコの対応が正しいということになるので、YESになります。

bool dp[102][102];

int main(){
  int T;
  cin >> T;

  string s;
  getline(cin, s);

  for(int CASE = 1; CASE <= T; CASE++){
    cout << "Case #" << CASE << ": ";

    getline(cin, s);

    memset(dp, 0, sizeof(dp));
    dp[0][0] = true;

    for(int i = 0; i < s.length(); i++){
      for(int j = 0; j <= s.length(); j++){
        if(!dp[i][j]) continue;

        bool col = (0 <= i - 1 && s[i - 1] == ':');

        if(s[i] == '('){
          dp[i + 1][j + 1] = true;
          if(col){
            dp[i + 1][j] = true;
          }
        }
        else if(s[i] == ')'){
          if(0 <= j - 1){
            dp[i + 1][j - 1] = true;
          }
          if(col){
            dp[i + 1][j] = true;
          }
        }
        else{
          dp[i + 1][j] = true;
        }
      }
    }

    cout << (dp[s.length()][0] ? "YES" : "NO") << endl;
  }
}

Problem C : Find the Min

「多分」、O(k)の解法

とりあえず、以下の性質は他の人も言ってますよね。

  • m[0]〜m[k-1]がどんな数列になるにしろ、m[1*k]〜m[2*k]には、0〜kの値がそれぞれ1個ずつ入る。
  • m[2*k+1]以降は、m[1*k]〜m[2*k]の周期が繰り返される。


2つ目の性質と、mapを利用して解いている人がいます( id:hirokazu1020さん : http://d.hatena.ne.jp/hirokazu1020/20130129/1359463036 )


僕の解法は、非常にこの人の解法と似ています。ただし、僕はmapではなく配列を使ってカウントしています。hirokazuさんの場合、m[0]~m[k-1]に出てくる、全ての数字の出現回数を数えていますが、実はカウントするのは0~kの数字の出現回数だけでいいです。これは、先ほど述べた1つ目の性質によるものです。いくらkより大きい数字をカウントしていたところで、周期の中にkより大きい数字が入ることはないわけだから、そんなカウントは必要ないわけです。

つまりこういう方針になります。

  • m[0]~m[k-1]に出現する、0以上k以下の値の出現回数を配列cntでカウントしておく(ただし、kより大きい数は無視する)。
    • 配列cntは、直前k個の数の出現回数を記憶した配列。
    • cnt[i]が0になっているときは、直前のk個の要素の中にiが含まれていないということになる。
  • 周期となるm[k]~m[k+k]の各要素を順番に求めていく。
  • 基本的に、0, 1, 2...の順番で小さい方から割り当てる。
  • ただし、添え字を後ろにずらしていく内に、使えるようになる数が出てくるので、その数の方が小さければ、そちらを使う。


以下のコードで、O(k)になってる(はず)。周期を求めるところがforとwhileの二重ループになっていて、一見O(k^2)に見えるかもですが、それは違います。外側のforループをk回まわしたとき、内側のwhileループがまわった回数を合計すると、それは最大でもk回にしかなりません。

typedef long long ll;

ll n, k;
ll a, b, c, r;
ll m[1000010];
ll cnt[1000010]; //カウント用配列

int main(){
  int T;
  cin >> T;

  for(int CASE = 1; CASE <= T; CASE++){
    cout << "Case #" << CASE << ": ";

    cin >> n >> k;
    cin >> a >> b >> c >> r;

    memset(cnt, 0, sizeof(cnt));
    m[0] = a;

    //0~kの数だけをカウントする
    if(m[0] <= k){
      cnt[m[0]] = 1;
    }

    for(int i = 1; i < k; i++){
      m[i] = (b * m[i - 1] + c) % r;

      //0~kの数だけをカウントする
      if(m[i] <= k){
        cnt[m[i]]++;
      }
    }

    //基本的に、このnowを周期に追加していく
    //1,2,3...の順番で小さい方を優先的に使うって言ってたやつです
    ll now = 0;

    vector<ll> cycle;

    //周期の要素である、k+1個の値を順番に求めます
    for(int i = k; i <= k + k; i++){
      //直前のk個より1個手前は、使われなくなる数字なので、これを取りだす
      ll val = (0 <= i - k - 1 ? m[i - k - 1] : INT_MAX);

      //0~kの値であれば、cntの配列を更新(直前のk個から1回分出現回数が減る)
      if(val <= k){
        cnt[val]--;
      }

      //小さい順に見て、次に使える数を探す
      //ここでnowを0からループさせていないのは、
      //[0]~[now-1]に使える数が存在しないから(valを除いて)
      while(cnt[now] > 0) now++;

      //新たに使えるようになる数(val)の方がnowより小さければ、それを使用
      if(val <= k && cnt[val] == 0 && val < now){
        cycle.push_back(val);
        cnt[val]++;
      }
      else{
        cycle.push_back(now);
        cnt[now]++;
      }
    }

    int idx = (n - k - 1) % cycle.size();
    cout << cycle[idx] << endl;
  }
}

AOJ : 1022 - Indian Puzzle

AOJ

問題概要

省略

解法

枝刈全探索で解けます。

枝刈手法

  • まず、再帰探索を開始する前に、式が合ってるか判定できるところは、全てしてしまいましょう。
  • 空白が埋まらないと式判定できない場所は、式判定に必要な空白が全て埋まった時点ですぐ式判定してしまいましょう。
  • 再帰関数で探索中に、盤面が成り立たないとわかった瞬間Noを返せば枝刈できます。

プログラム

300行近い、長いプログラムになってしまったので、参考にならないかもです。

#include <iostream>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cctype>
using namespace std;

#define INF 999999999

int h, w, n;
char t[12][12];
char p[12];

vector<int> blankX;
vector<int> blankY;

bool used[12];
bool isOperator[128];

//式の開始地点でないなら, -1が入る
//式の開始地点なら, どの座標の空白が埋まれば式判定できるか
//空白が埋まらなくても式判定できるなら, -2が入る
int gx0[12][12], gy0[12][12];
int gx1[12][12], gy1[12][12];

//構文解析用変数
int idxX;
int idxY;
int dir;

//右 下 左 上
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

//w*hの範囲内であるならばtrue
bool inBoard(int x, int y){
  return 0 <= x && x < w && 0 <= y && y < h;
}

//#でないマス目であるならばtrue
bool isWhite(int x, int y){
  if(!inBoard(x, y)) return false;
  return t[y][x] != '#';
}

//演算子が含まれるマスならばtrue
bool containsOperator(int x, int y){
  if(!inBoard(x, y)) return false;
  return isOperator[t[y][x]];
}

int N0(){
  if(!isdigit(t[idxY][idxX])){
    return INF;
  }

  string valStr;

  while(inBoard(idxX, idxY) && isdigit(t[idxY][idxX])){
    valStr += t[idxY][idxX];
    idxX += dx[dir];
    idxY += dy[dir];
  }

  if(valStr.length() == 1 || valStr[0] != '0'){
    return atoi(valStr.c_str());
  }
  return INF;
}

int Term(){
  int lv = N0();
  if(lv == INF) return INF;

  while(inBoard(idxX, idxY) && (t[idxY][idxX] == '*' || t[idxY][idxX] == '/')){
    char op = t[idxY][idxX];

    idxX += dx[dir];
    idxY += dy[dir];

    int rv = N0();
    if(rv == INF) return INF;

    if(op == '*'){
      lv *= rv;
    }
    else{
      if(rv == 0 || lv % rv != 0) return INF;
      lv /= rv;
    }
  }

  return lv;
}

int Ex(){
  int lv = Term();
  if(lv == INF) return INF;

  while(inBoard(idxX, idxY) && (t[idxY][idxX] == '+' || t[idxY][idxX] == '-')){
    char op = t[idxY][idxX];

    idxX += dx[dir];
    idxY += dy[dir];

    int rv = Term();
    if(rv == INF) return INF;

    if(op == '+') lv += rv;
    else          lv -= rv;
  }

  return lv;
}

bool isCorrectEq(){
  //左辺
  int lv = Ex();
  if(lv == INF) return false;

  //イコールがあるかどうか
  if(!inBoard(idxX, idxY) || t[idxY][idxX] != '=') return false;
  idxX += dx[dir];
  idxY += dy[dir];

  //右辺
  int rv = Ex();
  if(rv == INF) return false;

  if(isWhite(idxX, idxY)){
    return false;
  }

  return lv == rv;
}

bool isCorrectBoard(int x, int y){
  /*
  cout<<x<<","<<y<<endl;
  for(int i = 0; i < h; i++){
    cout << t[i] << endl;
  }
  cout<<"--\n";
  */

  for(int i = 0; i < h; i++){
    for(int j = 0; j < w; j++){
      if(gx0[i][j] == x && gy0[i][j] == y){
        idxX = j;
        idxY = i;
        dir = 0;

        if(!isCorrectEq()) return false;
      }
      if(gx1[i][j] == x && gy1[i][j] == y){
        idxX = j;
        idxY = i;
        dir = 1;

        if(!isCorrectEq()) return false;
      }
    }
  }

  return true;
}

bool dfs(int blankIdx){
  if(blankIdx == n){
    return true;
  }

  int x = blankX[blankIdx];
  int y = blankY[blankIdx];
  bool digitFlg = false;

  //必ず数字を入れなくてはいけないマスであるかチェック
  for(int i = 0; i < 4; i++){
    if(containsOperator(x + dx[i], y + dy[i])){
      digitFlg = true;
      break;
    }
  }
  if(isWhite(x + dx[0], y + dy[0]) + isWhite(x + dx[2], y + dy[2]) == 1){
    digitFlg = true;
  }
  if(isWhite(x + dx[1], y + dy[1]) + isWhite(x + dx[3], y + dy[3]) == 1){
    digitFlg = true;
  }

  //ピースを当てはめる
  for(int i = 0; i < n; i++){
    if(used[i]) continue;
    if(digitFlg && isOperator[p[i]]) continue;

    used[i] = true;
    t[y][x] = p[i];

    if(isCorrectBoard(x, y) && dfs(blankIdx + 1)) return true;

    used[i] = false;
  }

  return false;
}

int main(){
  isOperator['+'] = true;
  isOperator['-'] = true;
  isOperator['*'] = true;
  isOperator['/'] = true;
  isOperator['='] = true;

  while(cin >> h >> w, h || w){
    for(int i = 0; i < h; i++){
      cin >> t[i];
    }

    cin >> n;
    for(int i = 0; i < n; i++){
      cin >> p[i];
    }

    blankX.clear();
    blankY.clear();

    for(int i = 0; i < h; i++){
      for(int j = 0; j < w; j++){
        if(t[i][j] != '.') continue;
        blankX.push_back(j);
        blankY.push_back(i);
      }
    }

    memset(gx0, -1, sizeof(gx0));
    memset(gy0, -1, sizeof(gy0));
    memset(gx1, -1, sizeof(gx1));
    memset(gy1, -1, sizeof(gy1));

    for(int i = 0; i < h; i++){
      for(int j = 0; j < w; j++){
        if(t[i][j] == '#') continue;

        if(!isWhite(j + 1 * dx[2], i + 1 * dy[2]) &&
            isWhite(j + 1 * dx[0], i + 1 * dy[0]) &&
            isWhite(j + 2 * dx[0], i + 2 * dy[0])){
          int x = j;
          int y = i;

          gx0[i][j] = -2;
          gy0[i][j] = -2;

          while(inBoard(x, y) && isWhite(x, y)){
            if(t[y][x] == '.'){
              gx0[i][j] = x;
              gy0[i][j] = y;
            }
            x += dx[0];
            y += dy[0];
          }
        }
        if(!isWhite(j + 1 * dx[3], i + 1 * dy[3]) &&
            isWhite(j + 1 * dx[1], i + 1 * dy[1]) &&
            isWhite(j + 2 * dx[1], i + 2 * dy[1])){
          int x = j;
          int y = i;

          gx1[i][j] = -2;
          gy1[i][j] = -2;

          while(inBoard(x, y) && isWhite(x, y)){
            if(t[y][x] == '.'){
              gx1[i][j] = x;
              gy1[i][j] = y;
            }
            x += dx[1];
            y += dy[1];
          }
        }
      }
    }

    bool flg = isCorrectBoard(-2, -2);

    if(!flg){
      cout << "No\n";
      continue;
    }

    memset(used, 0, sizeof(used));
    cout << (dfs(0) ? "Yes" : "No") << endl;
  }
}