ホームに戻る
ヤジリン ソルバー
ヤジリンというパズルを解くプログラムです。
入力の書式
H W N
Y1 X1 D1 C1
Y2 X2 D2 C2
...
入力の説明
H 行の数
W 列の数
N 数の数
Y 数の行数(0-index)
X 数の列数(0-index)
D 矢印の方向 U:上 R:右 D:下 L:左
C 数の数
入力例
6 6 3
1 2 R 0
2 5 L 3
5 0 R 0
やっていること
数を参考に黒マスの位置はすべて試します。
線の位置は再帰処理でバックトラックしています。
バックトラックの探索は以下の条件で引き返します。
・不正な黒マスの検出
・袋小路の検出
・線がたどり着けない領域の検出
正確に回答が得られない場合の条件
・盤面の数によるヒントがあまりにも少ない場合
・盤面に与えられる数が不正な場合
・正解が存在しない場合
注意すべき点
作成時点で10x10程度の盤面で正解を出力できました。
正解は同じ解であっても時計回りと反時計周りの２通りを出力します。
正確な解の個数を出力できるかの検証はしていません。
/******
*
* Yajirin Solver
*
*
******/
#include <algorithm>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;
typedef long long ll;
#define sz size()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(c) (c).begin(), (c).end()
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define per(i,a,b) for(ll i=b-1LL;i>=(a);--i)
#define clr(a, b) memset((a), (b) ,sizeof(a))
#define ctos(c) string(1,c)
//#define print(x) cout<<#x<<" = "<<x<<endl;
#define MOD 1000000007
#define WHI 0 // 白マス
#define BLA 1 // 黒マス
#define NUM 2 // 数マス
#define SEK 4 // 線確定白マス
#define SEN 8 // 線マス
ll h,w,q;
ll sy,sx;
vector<pair<pair<ll,ll>, pair<ll,ll> > > vnl;
vector<vector<ll> > vv;
vector<vector<ll> > vans;
ll ans;
// 壁の判定
ll hit(ll y, ll x){
if(y<0)return 1;
if(x<0)return 1;
if(y>=h)return 1;
if(x>=w)return 1;
return 0;
}
// 表示
void display(){
string s = "URDL";
rep(y,0,h){
rep(x,0,w){
if(vv[y][x]==SEN&&vans[y][x]!=-1){
cout << s[vans[y][x]];
}
else{
cout << vv[y][x];
}
}
cout << endl;
}
cout << endl;
}
// 連続した黒マスのチェック
ll black_check(){
ll ret = 0;
rep(y,0,h){
rep(x,0,w){
if(y!=h-1&&(vv[y][x]==BLA&&vv[y+1][x]==BLA)){
ret = 1;
}
if(x!=w-1&&(vv[y][x]==BLA&&vv[y][x+1]==BLA)){
ret = 1;
}
}
}
return ret;
}
// 盤面の数と黒マスの数が適当かチェック
ll num_check(){
ll dy[4] = {-1,0,1,0};
ll dx[4] = {0,1,0,-1};
ll ret = 0;
rep(i,0,vnl.sz){
ll y,x,d,c;
y = vnl[i].fi.fi;
x = vnl[i].fi.se;
d = vnl[i].se.fi;
c = vnl[i].se.se;
ll count = 0;
while(1){
y += dy[d];
x += dx[d];
if(hit(y,x)==1)break;
if(BLA==vv[y][x])count++;
}
if(count!=c)ret = 1;
}
return ret;
}
// 完成しているかどうかをチェック
ll kansei_check(){
if(black_check()==1||num_check()==1)return 0;
rep(y,0,h){
rep(x,0,w){
if(vv[y][x]==SEK)return 0;
}
}
return 1;
}
// Union Find
vector<int> uf, usz;
int nc;
void init(int n){
vector<int> uf_(n);
vector<int> usz_(n, 1);
uf = uf_;
usz = usz_;
nc = n;
for(int i = 0; i < uf.size(); i++){
uf[i] = i;
}
}
int find(int a){
return (uf[a] == a) ? a : uf[a] = find(uf[a]);
}
void union_(int a, int b){
a = find(a);
b = find(b);
if(a != b){
if(usz[a] >= usz[b]){
swap(a, b);
}
uf[a] = b;
usz[b] += usz[a];
nc--;
}
}
int check(int a, int b){
return (find(a) == find(b)) ? 1 : 0;
}
int get_size(int a){
return usz[find(a)];
}
// 分断のチェック
ll bundan_check(){
init(h*w);
ll count = 0;
rep(y,0,h){
rep(x,0,w){
if(vv[y][x]==WHI||vv[y][x]==SEK)count++;
}
}
rep(y,0,h){
rep(x,0,w){
if(y!=h-1&&(vv[y][x]==WHI||vv[y][x]==SEK)&&(vv[y+1][x]==WHI||vv[y+1][x]==SEK)){
union_(y*w+x,(y+1)*w+x);
}
if(x!=w-1&&(vv[y][x]==WHI||vv[y][x]==SEK)&&(vv[y][x+1]==WHI||vv[y][x+1]==SEK)){
union_(y*w+x,y*w+x+1);
}
}
}
rep(y,0,h){
rep(x,0,w){
if(vv[y][x]==WHI||vv[y][x]==SEK){
if(get_size(y*w+x)!=count)return 1;
}
}
}
return 0;
}
// 線確定部分の検出
void senkakutei(stack<pair<pair<ll,ll>, ll> > &st){
ll dy[4] = {-1,0,1,0};
ll dx[4] = {0,1,0,-1};
// 数の条件から
rep(i,0,vnl.sz){
ll y,x,d,c;
y = vnl[i].fi.fi;
x = vnl[i].fi.se;
d = vnl[i].se.fi;
c = vnl[i].se.se;
vector<pair<ll,ll> > vp;
while(1){
y += dy[d];
x += dx[d];
if(hit(y,x)==1)break;
if(vv[y][x]==WHI){
st.push(mp(mp(y,x),vv[y][x]));
vv[y][x] = SEK;
}
}
}
// 黒マスの上下左右
rep(y,0,h){
rep(x,0,w){
if(vv[y][x]==BLA){
rep(i,0,4){
ll y1 = y+dy[i];
ll x1 = x+dx[i];
if(hit(y1,x1)==0){
if(vv[y1][x1]==WHI){
st.push(mp(mp(y1,x1),vv[y1][x1]));
vv[y1][x1] = SEK;
}
}
}
}
}
}
// 一方通行の前後
rep(y,0,h){
rep(x,0,w){
if(vv[y][x]==BLA){
rep(i,0,4){
ll y1 = y+dy[i];
ll x1 = x+dx[i];
ll y2 = y+dy[i]+dy[i];
ll x2 = x+dx[i]+dx[i];
if(hit(y1,x1)==0&&vv[y1][x1]==SEK){
ll y3 = y1 + dy[(i+1)%4];
ll x3 = x1 + dx[(i+1)%4];
ll y4 = y1 + dy[(i+3)%4];
ll x4 = x1 + dx[(i+3)%4];
if(hit(y2,x2)==1||(hit(y2,x2)==0&&(vv[y2][x2]==BLA||vv[y2][x2]==NUM))){
if(hit(y3,x3)==0&&vv[y3][x3]==WHI){
st.push(mp(mp(y3,x3),vv[y3][x3]));
vv[y3][x3] = SEK;
}
if(hit(y4,x4)==0&&vv[y4][x4]==WHI){
st.push(mp(mp(y4,x4),vv[y4][x4]));
vv[y4][x4] = SEK;
}
}
}
}
}
}
}
// 角の両側
rep(y,0,h){
rep(x,0,w){
if(vv[y][x]==BLA){
rep(i,0,4){
ll y1 = y+dy[i];
ll x1 = x+dx[i];
ll y2 = y+dy[i]*2;
ll x2 = x+dx[i]*2;
if(hit(y1,x1)==0){
ll y3 = y1 + dy[(i+1)%4];
ll x3 = x1 + dx[(i+1)%4];
ll y4 = y1 + dy[(i+3)%4];
ll x4 = x1 + dx[(i+3)%4];
if(hit(y3,x3)==1||(hit(y3,x3)==0&&(vv[y3][x3]==BLA||vv[y3][x3]==NUM))){
if(hit(y2,x2)==0&&vv[y2][x2]==WHI){
st.push(mp(mp(y2,x2),vv[y2][x2]));
vv[y2][x2] = SEK;
}
if(hit(y4,x4)==0&&vv[y4][x4]==WHI){
st.push(mp(mp(y4,x4),vv[y4][x4]));
vv[y4][x4] = SEK;
}
}
if(hit(y4,x4)==1||(hit(y4,x4)==0&&(vv[y4][x4]==BLA||vv[y4][x4]==NUM))){
if(hit(y2,x2)==0&&vv[y2][x2]==WHI){
st.push(mp(mp(y2,x2),vv[y2][x2]));
vv[y2][x2] = SEK;
}
if(hit(y3,x3)==0&&vv[y3][x3]==WHI){
st.push(mp(mp(y3,x3),vv[y3][x3]));
vv[y3][x3] = SEK;
}
}
}
}
}
}
}
}
// 袋小路の検出 黒マスで埋めて成り立つなら埋める
pair<ll,ll> fukurokoji1(ll yy, ll xx){
pair<ll,ll> p;
p.fi = -1;
p.se = -1;
ll dy[4] = {-1,0,1,0};
ll dx[4] = {0,1,0,-1};
rep(y,0,h){
rep(x,0,w){
if(y==yy&&x==xx)continue;
if(vv[y][x]!=WHI)continue;
ll count = 0;
rep(i,0,4){
ll y1 = y+dy[i];
ll x1 = x+dx[i];
if(y1==sy&&x1==sx)continue;
if(hit(y1,x1)==1)count++;
else{
if(vv[y1][x1]==NUM)count++;
if(vv[y1][x1]==SEN)count++;
}
}
if(count>=3){
p.fi = y;
p.se = x;
return p;
}
}
}
return p;
}
// 袋小路の検出 黒マスで埋められない場所が対象
ll fukurokoji2(ll yy, ll xx){
ll ret = 0;
ll dy[4] = {-1,0,1,0};
ll dx[4] = {0,1,0,-1};
rep(y,0,h){
rep(x,0,w){
if(y==yy&&x==xx)continue;
if(vv[y][x]!=WHI&&vv[y][x]!=SEK)continue;
ll count = 0;
rep(i,0,4){
ll y1 = y+dy[i];
ll x1 = x+dx[i];
if(y1==sy&&x1==sx)continue;
if(hit(y1,x1)==1)count++;
else{
if(vv[y1][x1]==BLA)count++;
if(vv[y1][x1]==NUM)count++;
if(vv[y1][x1]==SEN)count++;
}
}
if(count>=3){
ret = 1;
}
}
}
return ret;
}
// バックトラック本体
void f2(ll y, ll x, ll c){
if(hit(y,x)==1)return;
if(vv[y][x]==BLA)return;
if(vv[y][x]==NUM)return;
if(sy==y&&sx==x&&c>0){
stack<pair<pair<ll,ll>,ll> > st;
rep(y,0,h){
rep(x,0,w){
if(vv[y][x]==WHI){
st.push(mp(mp(y,x),vv[y][x]));
vv[y][x] = BLA;
}
}
}
if(kansei_check()==1){
ans++;
display();
}
while(!st.empty()){
pair<pair<ll,ll>, ll> pp = st.top();st.pop();
vv[pp.fi.fi][pp.fi.se] = pp.se;
}
return;
}
if(vv[y][x]==SEN)return;
if(bundan_check()==1)return;
stack<pair<pair<ll,ll>,ll> > st;
while(1){
pair<ll,ll> p = fukurokoji1(y,x);
ll y1 = p.fi;
ll x1 = p.se;
if(y1==-1)break;
st.push(mp(mp(y1,x1),vv[y1][x1]));
vv[y1][x1] = BLA;
}
if(fukurokoji2(y,x)==1||num_check()==1){
while(!st.empty()){
pair<pair<ll,ll>, ll> pp = st.top();st.pop();
vv[pp.fi.fi][pp.fi.se] = pp.se;
}
return;
}
st.push(mp(mp(y,x),vv[y][x]));
vv[y][x] = SEN;
ll dy[4] = {-1,0,1,0};
ll dx[4] = {0,1,0,-1};
rep(i,0,4){
ll y1 = y+dy[i];
ll x1 = x+dx[i];
vans[y][x] = i;
f2(y1,x1,c+1);
}
while(!st.empty()){
pair<pair<ll,ll>, ll> pp = st.top();st.pop();
vv[pp.fi.fi][pp.fi.se] = pp.se;
}
}
// 再帰のスタート位置を決定
void f1(){
ll y = 0;
ll x = 0;
rep(y,0,h){
rep(x,0,w){
if(vv[y][x]==SEK){
sy = y;
sx = x;
f2(y,x,0);
return;
}
}
}
}
// 解く
void solve(){
if(black_check()==1)return;
if(num_check()==1)return;
stack<pair<pair<ll,ll>, ll> > st;
senkakutei(st);
while(1){
pair<ll,ll> p = fukurokoji1(-1,-1);
ll y1 = p.fi;
ll x1 = p.se;
if(y1==-1)break;
st.push(mp(mp(y1,x1),vv[y1][x1]));
vv[y1][x1] = BLA;
}
if(fukurokoji2(-1,-1)==1||num_check()==1){
while(!st.empty()){
pair<pair<ll,ll>, ll> pp = st.top();st.pop();
vv[pp.fi.fi][pp.fi.se] = pp.se;
}
return;
}
f1();
while(!st.empty()){
pair<pair<ll,ll>, ll> pp = st.top();st.pop();
vv[pp.fi.fi][pp.fi.se] = pp.se;
}
}
// 数の条件から黒マスを全探索で埋める
void make_board(){
ll dy[4] = {-1,0,1,0};
ll dx[4] = {0,1,0,-1};
vector<vector<pair<ll,ll> > > vvp;
rep(i,0,vnl.sz){
ll y,x,d,c;
y = vnl[i].fi.fi;
x = vnl[i].fi.se;
vv[y][x] = NUM;
}
rep(i,0,vnl.sz){
ll y,x,d,c;
y = vnl[i].fi.fi;
x = vnl[i].fi.se;
d = vnl[i].se.fi;
c = vnl[i].se.se;
vector<pair<ll,ll> > vp;
while(1){
y += dy[d];
x += dx[d];
if(hit(y,x)==1)break;
if(NUM!=vv[y][x]){
vp.pb(mp(y,x));
}
}
vvp.pb(vp);
}
vector<vector<ll> > vv1;
rep(i,0,vvp.sz){
vector<ll> v;
ll a = vvp[i].sz;
ll c = vnl[i].se.se;
if(a-c<0)return;
rep(j,0,a-c)v.pb(0);
rep(j,0,c)v.pb(1);
vv1.pb(v);
}
ll flag = 0;
while(1){
ll index = 0;
while(1){
bool res = next_permutation(all(vv1[index]));
if(res==false){
sort(all(vv1[index]));
index++;
if(index==vv1.sz){
flag = 1;
break;
}
}
else break;
}
stack<pair<ll,ll> > st;
rep(i,0,vv1.sz){
rep(j,0,vv1[i].sz){
if(vv1[i][j]==1){
ll y = vvp[i][j].fi;
ll x = vvp[i][j].se;
st.push(mp(y,x));
vv[y][x] = BLA;
}
}
}
solve();
while(!st.empty()){
pair<ll,ll> p = st.top();st.pop();
vv[p.fi][p.se] = WHI;
}
if(flag==1)break;
}
}
int main(){
cin>>h>>w>>q;
rep(i,0,q){
ll y,x,d,c;
cin>>y>>x;
string s;
cin>>s;
if(s[0]=='U')d=0;
if(s[0]=='R')d=1;
if(s[0]=='D')d=2;
if(s[0]=='L')d=3;
cin>>c;
vnl.pb(mp(mp(y,x),mp(d,c)));
}
vector<vector<ll> > _vv(h,vector<ll>(w,WHI));
vv = _vv;
vector<vector<ll> > _vans(h,vector<ll>(w,-1));
vans = _vans;
make_board();
return 0;
}
