AOJ 0263 - Beat Panel (ビートパネル)
解法
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 開始時間になったら、このページの一番上にコンテストページへのリンクが現れます。 |
備考 | 蟻本持ってると解きやすいかも(?) |
会津合宿の宣伝
- 会津合宿2013: http://kokucheese.com/event/index/106462/
- 9/3 14:30-17:30 : 2Dセット
- 9/4 11:00-16:00 : 会津大学セット
- 9/5 10:00-15:00 : @k_operafanさん、@todo341さんのセット
- 全て、AOJで開催されます。Day2, 3にも是非ご参加ください
UVa : 361 - Cops and Robbers
問題概要
点集合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点から成る三角形に、点が含まれている」ということになります。
点集合の任意の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
問題概要
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の倍数になると、正方形の辺が1本増えるため
- kを追加することで、使用している棒の長さの合計が、len*(i+1)より小さくなるならば
- dp[i][j | (1 << k)]が1になる
- もし、長さの合計がlen*(i+1)より大きくなってしまう場合は、棒を折り曲げたりしないと、正方形の辺を増やすことができないので無視
- kを追加することで、使用している棒の長さの合計が、lenの倍数になるならば
プログラム
#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
問題概要
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
問題概要
省略
解法
枝刈全探索で解けます。
枝刈手法
プログラム
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; } }