20 条题解
-
2
Sky1231 (sky1231) LV 10 @ 2017-08-14 11:46:33
#include <cmath> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; struct s_1 { int x,y,z; }ans[6]; struct s_2 { int a[5][7]; int s[11]; }qhy[100+1]; int n,sum; int b[5][7]; int check_1(int now) { for (int i=0;i<=4;i++) if (qhy[now].a[i][0]!=0) return 0; return 1; } //xq???? int check_xq_1(int now) { for (int i=1;i<=10;i++) if (qhy[now].s[i]==1||qhy[now].s[i]==2) return 0; return 1; } void copy_1(int x,int y) { for (int i=0;i<=4;i++) for (int j=0;j<=6;j++) qhy[x].a[i][j]=qhy[y].a[i][j]; for (int i=1;i<=10;i++) qhy[x].s[i]=qhy[y].s[i]; } int drop_1(int now) { int flag=0; for (int i=0;i<=4;i++) for (int j=1;j<=6;j++) if (qhy[now].a[i][j]!=0) { int cnt; for (cnt=j;cnt>0&&qhy[now].a[i][cnt-1]==0;cnt--,flag=1) swap(qhy[now].a[i][cnt-1],qhy[now].a[i][cnt]); } return flag; } //xq???? int xq_1(int now) { int flag=0; memset(b,0,sizeof(b)); for (int i=0;i<=6;i++) for (int j=0;j<=2;j++) if (qhy[now].a[j][i]!=0&&qhy[now].a[j][i]==qhy[now].a[j+1][i]&&qhy[now].a[j][i]==qhy[now].a[j+2][i]) b[j][i]=b[j+1][i]=b[j+2][i]=1; for (int i=0;i<=4;i++) for (int j=0;j<=4;j++) if (qhy[now].a[i][j]!=0&&qhy[now].a[i][j]==qhy[now].a[i][j+1]&&qhy[now].a[i][j]==qhy[now].a[i][j+2]) b[i][j]=b[i][j+1]=b[i][j+2]=1; for (int i=0;i<=4;i++) for (int j=0;j<=6;j++) if (b[i][j]) { int temp=qhy[now].a[i][j]; qhy[now].s[temp]--; qhy[now].a[i][j]=0; flag=1; } return flag; } int dfs_1(int now,int step) { if (step>n) return check_1(now); if (check_xq_1(now)==0) return 0; for (int i=0;i<=4;i++) for (int j=0;j<=6;j++) { if (qhy[now].a[i][j]==0) break; ans[step].x=i,ans[step].y=j; if (i<4&&qhy[now].a[i][j]!=qhy[now].a[i+1][j]) { ans[step].z=1; sum++; copy_1(sum,now); swap(qhy[sum].a[i][j],qhy[sum].a[i+1][j]); while (drop_1(sum)||xq_1(sum)) ; if (dfs_1(sum,step+1)) return 1; sum--; } if (i>0&&qhy[now].a[i-1][j]==0) { ans[step].z=-1; sum++; copy_1(sum,now); swap(qhy[sum].a[i-1][j],qhy[sum].a[i][j]); while (drop_1(sum)||xq_1(sum)) ; if (dfs_1(sum,step+1)) return 1; sum--; } } return 0; } int main() { while (~scanf("%d",&n)) { sum=0; for (int i=0;i<=4;i++) for (int j=0;j<=7;j++) { int temp; scanf("%d",&temp); if (temp==0) break; qhy[0].a[i][j]=temp; qhy[0].s[temp]++; } if (dfs_1(0,1)) { for (int i=1;i<=n;i++) printf("%d %d %d\n",ans[i].x,ans[i].y,ans[i].z); } else printf("%d\n",-1); } }-
很H2O的題
-
-
1
#include <algorithm> #include <cstdio> #include <cstdlib> #include <cstring> using std :: swap; int s[6][8],n; struct T { int x,y,z; }ans[6]; inline bool check(int tmp[6][8]) { bool pd[6][8],flag = false; memset(pd,false,sizeof(pd)); for (int i = 0;i <= 5;i++) for (int j = 0;j <= 7;j++) if (tmp[i][j]) { if (i <= 3 && tmp[i][j] == tmp[i+1][j] && tmp[i+1][j] == tmp[i+2][j]) pd[i][j] = pd[i+1][j] = pd[i+2][j] = true; if (j <= 5 && tmp[i][j] == tmp[i][j+1] && tmp[i][j+1] == tmp[i][j+2]) pd[i][j] = pd[i][j+1] = pd[i][j+2] = true; } for (int i = 0;i < 5;i++) for (int j = 0;j < 7;j++) if (pd[i][j]) { tmp[i][j] = 0; flag = true; } return flag; } void dfs(int tot,int map[6][8]) { if (tot == n) { bool flag = true; for (int i = 0;i < 5;i++) for (int j = 0;j < 7;j++) if (map[i][j]) { flag = false; break; } if (flag) { for (int i = 1;i <= n;i++) printf("%d %d %d\n",ans[i].x,ans[i].y,ans[i].z); exit(false); } return; } int cnt[11]; memset(cnt,0,sizeof(cnt)); for (int i = 0;i < 5;i++) for (int j = 0;j < 7;j++) cnt[map[i][j]]++; for (int i = 1;i <= 10;i++) if (cnt[i] == 1 || cnt[i] == 2) return; for (int i = 0;i < 4;i++) for (int j = 0;j < 7;j++) if (map[i][j] != map[i+1][j]) { int tmp[6][8]; memcpy(tmp,map,sizeof(tmp)); if (tmp[i][j]) { ans[tot+1].x = i; ans[tot+1].y = j; ans[tot+1].z = 1; } else { ans[tot+1].x = i+1; ans[tot+1].y = j; ans[tot+1].z = -1; } swap(tmp[i][j],tmp[i+1][j]); for (int i = 0;i < 5;i++) { int t = 0; for(int j = 0;j < 7;j++) { int l = tmp[i][j]; tmp[i][j] = 0; if (l) tmp[i][t++] = l; } } while (check(tmp)) { for (int i = 0;i < 5;i++) { int t = 0; for(int j = 0;j < 7;j++) { int l = tmp[i][j]; tmp[i][j] = 0; if (l) tmp[i][t++] = l; } } } dfs(tot+1,tmp); } } int main() { //freopen("mayan.in","r",stdin); //freopen("mayan.out","w",stdout); scanf("%d",&n); for (int i = 0;i < 5;i++) { int x,t = 0; read : scanf("%d",&x); if (x) { s[i][t++] = x; goto read; } } dfs(0,s); printf("-1"); return 0; }-
唐复之 @ 2018-07-25 18:29:48
悄悄抄走...............(orz)
-
-
0
千万要注意读入！！！！！！！！！
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
struct node{
int x,y,fa;
}path[10];
int n,map[5][10]={0},book[5][7]={0};
bool finish(){
int i,j;
for(i=0;i<5;i++){
for(j=0;j<7;j++){
if(map[i][j]!=0) return false;
}
}
return true;
}
void swap(int *a,int *b){
int *c;
c=a;a=b;b=c;
}
void fall(int i){
int j;
for(j=0;j<7;j++){
if(map[i][j]==0){
int k=j;
while(k<7){
if(map[i][k]!=0){
swap(map[i][k],map[i][j]);
break;
}
k++;
}
}
}
}
bool check(){
int i,j,flag=0;
for(i=0;i<5;i++){
for(j=0;j<5&&map[i][j];j++){
if(map[i][j]==map[i][j+1]&&map[i][j+1]==map[i][j+2]){
book[i][j]=1;book[i][j+1]=1;book[i][j+2]=1; flag=1;
}
}
}
for(j=0;j<7;j++){
for(i=0;i<3;i++){
if(!map[i][j]) continue;
if(map[i][j]==map[i+1][j]&&map[i+1][j]==map[i+2][j]){
book[i][j]=1;book[i+1][j]=1;book[i+2][j]=1;flag=1;
}
}
}
/*for(i=0;i<5;i++){
for(j=0;j<7;j++){
cout<<book[i][j]<<" ";
}
cout<<endl;
}
cout<<endl;*/
return flag;
}
void clear(){
int i,j;
for(i=0;i<5;i++){
for(j=0;j<7;j++){
if(book[i][j]){
map[i][j]=0;book[i][j]=0;
}
}
}
for(i=0;i<5;i++) fall(i);
}
void dfs(int step){
int graph[5][10];
memcpy(graph,map,sizeof(map));
int i,j,k;
if(finish()){
for(i=1;i<=n;i++){
cout<<path[i].x<<" "<<path[i].y<<" "<<path[i].fa<<endl;
}
exit(0);
}
if(step>n) return;
for(i=0;i<5;i++){
for(j=0;j<7&&map[i][j];j++){
for(k=1;k>=-1;k-=2){
//if(!((step==1&&i==0&&j==1&&k==1)||(step==2&&i==1&&j==1&&k==1)||(step==3&&i==1&&j==3&&k==1)||(step==4&&i==1&&j==2&&k==1)||(step==5&&i==2&&j==0&&k==1))) continue;
int newx=i+k;
if((newx>=5)||(newx<0)) continue;
if(k==-1&&map[newx][j]!=0) continue;
if(map[i][j]==map[newx][j]) continue;
swap(map[newx][j],map[i][j]);
fall(i);fall(newx);
while(check()){
clear();
}
path[step].x=i;path[step].y=j;path[step].fa=k;
dfs(step+1);
memcpy(map,graph,sizeof(graph));
}
}
}
}
int main(){
freopen("mayan9.in","r",stdin);
int i,j,tmp;
cin>>n;
for(i=0;i<5;i++){
for(j=0;j<=7;j++){
cin>>tmp;
if(tmp==0) break;
map[i][j]=tmp;
}
}
dfs(1);
cout<<"-1"<<endl;
return 0;
}
-
0
//代码风格很诡异……
//剪枝1：若某个方块左边有方块，那么这个方块就不需要左移（这个剪枝非常重要）
//剪枝2：若某个颜色当前不到3个直接return#include <cstdlib>
#include <cstdio>
#include <cstring>using namespace std;
inline bool combo(int x , int y , int z)
{
return (x == y && y == z);
}
inline void swap(int &a , int &b)
{
int t = a; a = b; b = t;
}struct record
{
int x , y , dir;void Load(int X , int Y , int Dir)
{
x = X , y = Y , dir = Dir;
}
}rec[7];struct Map
{
int a[6][8] , d[6][8];
void Clean()
{
for (int i = 1 , j ; i <= 5 ; ++i)
for (j = 1 ; j <= a[i][0] ; ++j)
if (d[i][j] == 1)
a[i][j] = 0;
}
void Drop(int row)
{
int tmp[8] = {0} , pos = 0;
for (int j = 1 ; j <= 7 ; ++j)
{
if (a[row][j] != 0)
tmp[++pos] = a[row][j];
a[row][j] = 0;
}
a[row][0] = pos;
for (int j = 1 ; j <= pos ; ++j)
a[row][j] = tmp[j];
}
void DropDown()
{
for (int i = 1 ; i <= 5 ; ++i)
Drop(i);
}
bool Collapse(int x , int y)
{
bool ret = 0;
if (x >= 2 && x <= 4)
{
if (combo(a[x - 1][y] , a[x][y] , a[x + 1][y]))
{
d[x - 1][y] = d[x][y] = d[x + 1][y] = 1;
ret = 1;
}
}
if (y >= 2 && y < a[x][0])
{
if (combo(a[x][y - 1] , a[x][y] , a[x][y + 1]))
{
d[x][y - 1] = d[x][y] = d[x][y + 1] = 1;
ret = 1;
}
}
return ret;
}
void Read(int i , int b[])
{
for (int j = 0 ; j <= b[0] ; ++j)
a[i][j] = b[j];
}
void Move(int x , int y , int dir)
{
swap(a[x][y] , a[x + dir][y]);
DropDown();bool flag = 1 , tmp;
while (flag)
{
memset(d , 0 , sizeof(d));
flag = 0;
for (int i = 1 , j ; i <= 5 ; ++i)
for (j = 1 ; j <= a[i][0] ; ++j)
{
tmp = Collapse(i , j);
flag = flag || tmp;
}
Clean();
DropDown();
}
}
int CountMin()
{
int color[10] = {0} , min = 99;
for (int i = 1 , j ; i <= 5 ; ++i)
for (j = 1 ; j <= a[i][0] ; ++j)
++color[a[i][j]];
for (int i = 1 ; i <= 9 ; ++i)
if (color[i] != 0 && color[i] < min)
min = color[i];
return min;
}
bool Empty()
{
for (int i = 1 ; i <= 5 ; ++i)
if (a[i][0] != 0)
return 0;
return 1;
}
bool Exist(int x , int y)
{
return a[x][y] != 0;
}
void Print()
{
for (int i = 1 , j ; i <= 5 ; ++i)
{
for (j = 1 ; j <= a[i][0] ; ++j)
printf("%d " , a[i][j]);
printf("\n");
}
printf("\n");
}
}status;int N;
void Init()
{
int tmp[10] = {0};scanf("%d" , &N);
for (int i = 1 , j ; i <= 5 ; ++i)
{
for (j = 1 ; j <= 8 ; ++j)
{
scanf("%d" , tmp + j);
if (tmp[j] == 0)
break;
}
tmp[0] = j - 1;
status.Read(i , tmp);
}
}
void DFS(int i)
{
if (i > N)
{
if (status.Empty())
{
for (int j = 1 ; j <= N ; ++j)
printf("%d %d %d\n" , rec[j].x - 1 , rec[j].y - 1 , rec[j].dir);
exit(0);
}
return;
}
if (status.CountMin() < 3)
return;Map bak = status;
for (int j = 1 , k ; j <= 5 ; ++j)
for (k = 1 ; k <= 7 ; ++k)
{
if (!status.Exist(j , k))
continue;
if (j + 1 <= 5 && status.a[j + 1][k] != status.a[j][k])
{
rec[i].Load(j , k , 1);
status.Move(j , k , 1);
DFS(i + 1);status = bak;
}
if (j - 1 > 0 && status.a[j - 1][k] == 0)
{
rec[i].Load(j , k , -1);
status.Move(j , k , -1);
DFS(i + 1);status = bak;
}
}
}int main()
{
Init();
DFS(1);
printf("-1\n");
return 0;
} -
0
测试数据 #0: Accepted, time = 15 ms, mem = 556 KiB, score = 10
测试数据 #1: Accepted, time = 7 ms, mem = 556 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 556 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 560 KiB, score = 10
测试数据 #4: Accepted, time = 359 ms, mem = 556 KiB, score = 10
测试数据 #5: Accepted, time = 656 ms, mem = 552 KiB, score = 10
测试数据 #6: Accepted, time = 125 ms, mem = 552 KiB, score = 10
测试数据 #7: Accepted, time = 218 ms, mem = 552 KiB, score = 10
测试数据 #8: Accepted, time = 421 ms, mem = 552 KiB, score = 10
测试数据 #9: Accepted, time = 2515 ms, mem = 552 KiB, score = 10
Accepted, time = 4331 ms, mem = 560 KiB, score = 100#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int a[7][8],b[7][8],temp[6][7][8];
bool vis[7][8];
int n;
int kk;
struct ok
{
int x,y,z;
};
ok ans[6];
void isok(int x1,int y1,int x2,int y2,int step)
{
if(a[x1][y1]==0)
{
ans[step].x=x2-1;ans[step].y=y2-1;ans[step].z=-1;
}
else
{
ans[step].x=x1-1;ans[step].y=y1-1;ans[step].z=1;
}
}
void change(int x1,int y1,int x2,int y2)
{
swap(a[x1][y1],a[x2][y2]);
}
void copy()
{
for(int i=1;i<=5;i++)
for(int j=1;j<=7;j++)
b[i][j]=a[i][j];
}
void bigcopy_a_temp(int x)
{
for(int i=1;i<=5;i++)
for(int j=1;j<=7;j++)
temp[x][i][j]=a[i][j];
}
void bigcopy_temp_a(int x)
{
for(int i=1;i<=5;i++)
for(int j=1;j<=7;j++)
a[i][j]=temp[x][i][j];
}
bool check()
{
for(int i=1;i<=5;i++)
for(int j=1;j<=7;j++)
if(b[i][j]!=a[i][j])
return false;
return true;
}
void down()
{
copy();
for(int i=1;i<=5;i++)
for(int j=7;j>=2;j--)
if(a[i][j]!=0 && a[i][j-1]==0) swap(a[i][j],a[i][j-1]);
if(!check())
down();
else
return;
}
void clear1();
void clear2();
int cmp(ok p,ok q)
{
if(p.x!=q.x)
return p.x<q.x;
else
if(p.y!=q.y)
return p.y>q.y;
else
return p.z>q.z;
}
void print()
{
//sort(ans+1,ans+n+1,cmp);
for(int i=1;i<=n;i++)
cout<<ans[i].x<<" "<<ans[i].y<<" "<<ans[i].z<<endl;
cout<<endl;
}
void make(int x1,int y1,int x2,int y2)
{
change(x1,y1,x2,y2);
down();
clear1();
clear2();
clear1();
clear2();
}
void dfs(int step)
{
if(step>n)
{
memset(b,0,sizeof(b));
if(check())
{
print();
exit(0);
}
return;
}
for(int i1=1;i1<=5;i1++)
for(int j1=1;j1<=7;j1++)
{
int i2=i1+1,j2=j1;
if(i2<=5 && (a[i1][j1]!=0 || a[i2][j2]!=0) && a[i1][j1]!=a[i2][j2] && !vis[i1][j1])
{
bigcopy_a_temp(step);vis[i1][j1]=true;isok(i1,j1,i2,j2,step);
make(i1,j1,i2,j2);
dfs(step+1);
bigcopy_temp_a(step);vis[i1][j1]=false;
}
}
}
int main()
{
cin>>n;
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(temp,0,sizeof(temp));
memset(vis,false,sizeof(vis));
memset(ans,0,sizeof(ans));
for(int i=1;i<=5;i++)
{
int j=1;
while(true)
{
int temp; cin>>temp;
if(temp==0) break;
a[i][j]=temp;
j++;
}
}
for(int x1=1;x1<=5;x1++)
for(int y1=1;y1<=7;y1++)
{
int x2=x1+1,y2=y1;
if(x2<=5 && (a[x1][y1]!=0 || a[x2][y2]!=0) && a[x1][y1]!=a[x2][y2])
{
bigcopy_a_temp(1);vis[x1][y1]=true;isok(x1,y1,x2,y2,1);
make(x1,y1,x2,y2);
dfs(2);
bigcopy_temp_a(1);vis[x1][y1]=false;
}
}
cout<<"-1"<<endl;
return 0;
}
void clear1()
{
copy();
for(int p=1;p<=5;p++)
{
int q=7;
while(true)
{
if(a[p][q]!=0)
{
int count1=0,g1;
for(g1=q;g1>=1;g1--)
if(a[p][g1]!=a[p][q])
break;
else
count1++;
if(count1>=3)
{
for(int kk=g1+1;kk<=q;kk++)
{
int count2=0,count3=0,g2,g3;
for(g2=p;g2>=1;g2--)
if(a[g2][kk]!=a[p][q])
break;
else
count2++;
for(g3=p;g3<=5;g3++)
if(a[g3][kk]!=a[p][q])
break;
else
count3++;
if(count2+count3-1>=3)
for(int c=g2+1;c<=g3-1;c++)
a[c][kk]=0;
}
for(int c=g1+1;c<=q;c++)
a[p][c]=0;
down();
}
}
q--;
if(q==0) break;
}
}
if(!check())
{
clear1();
clear2();
}
else
{
clear2();
return;
}
}
void clear2()
{
copy();
for(int q=1;q<=7;q++)
{
int p=5;
while(true)
{
if(a[p][q]!=0)
{
int count1=0,g1;
for(g1=p;g1>=1;g1--)
if(a[g1][q]!=a[p][q])
break;
else
count1++;
if(count1>=3)
{
for(int kk=g1+1;kk<=p;kk++)
{
int count2=0,count3=0,g2,g3;
for(g2=q;g2>=1;g2--)
if(a[kk][g2]!=a[p][q])
break;
else
count2++;
for(g3=q;g3<=7;g3++)
if(a[kk][g3]!=a[p][q])
break;
else
count3++;
if(count2+count3-1>=3)
for(int c=g2+1;c<=g3-1;c++)
a[kk][c]=0;
}
for(int c=g1+1;c<=p;c++)
a[c][q]=0;
down();
}
}
p--;
if(p==0) break;
}
}
if(!check())
{
clear1();
clear2();
}
else
return;
} -
0
#include<cstdio>
#include<algorithm>
using namespace std;const int MaxQ=2000000;
typedef int Map[7][5],Step[5][3];
struct State {Map A;Step B;} Fir;
int f,w,step,cnt;inline int Go_Down(Map A)
{
Map B;int Flag=0;
for (int i=0;i<7;i++) for (int j=0;j<5;j++) B[i][j]=0;
//Down
for (int j=0;j<5;j++)
{
int Last=0;
for (int i=0;i<7;i++) if (A[i][j]) A[Last++][j]=A[i][j];
for (int i=Last;i<7;i++) A[i][j]=0;
}
//Merge
for (int i=1;i<6;i++)
for (int j=0;j<5;j++)
if (A[i][j]&&A[i][j]==A[i-1][j]&&A[i][j]==A[i+1][j]) B[i][j]=B[i-1][j]=B[i+1][j]=1;
for (int i=0;i<7;i++)
for (int j=1;j<4;j++)
if (A[i][j]&&A[i][j]==A[i][j-1]&&A[i][j]==A[i][j+1]) B[i][j]=B[i][j-1]=B[i][j+1]=1;
for (int i=0;i<7;i++)
for (int j=0;j<5;j++)
if (B[i][j]) A[i][j]=0,Flag=1;
return Flag;
}
inline int Cut(Map A,int nows)
{
//Cut 1
int cc[11];
for (int i=1;i<cnt;i++) cc[i]=0;
for (int i=0;i<7;i++) for (int j=0;j<5;j++) if (A[i][j]) cc[A[i][j]]++;
for (int i=1;i<cnt;i++) if (cc[i]&&cc[i]<3) return 1;
//Cut 2
int Dc[5][11],sum=0,Max=0,ttmp=0;
for (int i=1;i<=cnt;i++) for (int j=0;j<5;j++) Dc[j][i]=0;
for (int j=0;j<5;j++) for (int i=0;i<7;i++) Dc[j][A[i][j]]++,ttmp+=A[i][j];
for (int co=1;co<=cnt;co++)
{
int tmp=0;
for (int i=0;i<5;i++)
if (Dc[i][co]&&Dc[i][co]<3)
for (int j=1;j<5;j++)
{
if (i+j<5&&Dc[i+j][co]) {tmp=max(tmp,j);break;}
if (i-j>=0&&Dc[i-j][co]) {tmp=max(tmp,j);break;}
}
Max=max(Max,tmp-1);
sum+=max(tmp-1,0);
}
if (max(Max+nows-1,sum/2)+(ttmp!=0)>step) return 1;
return 0;
}
inline void check(State S,int s)
{
for (int i=0;i<7;i++)
for (int j=0;j<5;j++) if (S.A[i][j]) return;
for (int i=0;i<s;i++)
{
for (int j=0;j<3;j++) printf("%d ",S.B[i][j]);
puts("");
}
exit(0);
}
inline void DFS(State x,int s)
{
check(x,s);
if (s==step) return;
for (int j=0;j<5;j++)
for (int i=0;i<7;i++)
{
if (x.A[i][j]==0) break;
if (j<4&&x.A[i][j]&&x.A[i][j]!=x.A[i][j+1])
{
State y=x;
swap(y.A[i][j],y.A[i][j+1]);while (Go_Down(y.A));
if (!Cut(y.A,s+1))
{
y.B[s][0]=j;y.B[s][1]=i;y.B[s][2]=1;
DFS(y,s+1);
}
}
if (j>0&&x.A[i][j]&&!x.A[i][j-1])
{
State y=x;
swap(y.A[i][j],y.A[i][j-1]);while (Go_Down(y.A));
if (!Cut(y.A,s+1))
{
y.B[s][0]=j;y.B[s][1]=i;y.B[s][2]=-1;
DFS(y,s+1);
}
}
}
}int main()
{
freopen("mayan.in","r",stdin);
freopen("mayan.out","w",stdout);
scanf("%d",&step);
for (int i=0;i<5;i++)
for (int j=0;j<8;j++)
{
scanf("%d",&Fir.A[j][i]),cnt=max(cnt,Fir.A[j][i]);
if (Fir.A[j][i]==0) break;
}
DFS(Fir,0);
puts("-1");
} -
0
求各位大大们看一下哪里错了，好像是死循环了但是用watch看不出来，我是用pascal语言的
var map:array[0..4,0..6]of longint;
x,y,did:array[0..5]of longint;
n,i,j:longint;
function pd:boolean;
var i,j:longint;
delete:array[0..4,0..6]of boolean;
begin
fillchar(delete,sizeof(delete),#0);
pd:=true;
for i:=0 to 2 do
for j:=0 to 4 do
begin
if ((map[i,j]=map[i+1,j])and(map[i+1,j]=map[i+2,j])) then
begin delete[i,j]:=true;delete[i+1,j]:=true;delete[i+2,j]:=true;end;
if ((map[i,j+1]=map[i,j])and(map[i,j+2]=map[i,j+1])) then
begin delete[i,j]:=true;delete[i,j+1]:=true;delete[i,j+2]:=true;end;
end;
for i:=0 to 4 do
for j:=0 to 6 do
if delete[i,j] then begin pd:=true;map[i,j]:=0;end;
end;procedure fall;
var k,i,j:longint;
begin
for i:=0 to 4 do
for j:=0 to 6 do
begin
k:=j;
while ((k>0)and(map[i,k-1]=0)) do
begin
dec(k);
map[i,k]:=map[i,k+1];
map[i,k+1]:=0;
end;
end;
end;
procedure print(k:longint);
var i,j:longint;
begin
for i:=0 to 4 do
for j:=0 to 6 do
if map[i,j]>0 then exit;
for i:=1 to k do writeln(x[i],' ',y[i],' ',did[i]);
close(input);close(output);halt;
end;procedure go(k:longint);
var i,j,t:longint;
jl:array[0..4,0..6]of longint;
begin
writeln(k);
for i:=0 to 3 do
for j:=0 to 6 do
begin
if (x[k-1]=i)and(y[k-1]=j) then continue;
if map[i,j]=map[i+1,j] then continue;
if map[i,j]=0 then
begin
x[k]:=i+1;y[k]:=j;did[k]:=-1;
end else
begin
x[k]:=i;y[k]:=j;did[k]:=1;
end;
jl:=map;
t:=map[i,j];map[i,j]:=map[i+1,j];map[i+1,j]:=t;
fall;
while pd do fall;
if k<n then go(k+1) else print(k);
map:=jl;
end;
end;begin
assign(input,'mayan.in');reset(input);
//assign(output,'mayan.out');rewrite(output);
readln(n);
for i:=0 to 4 do
for j:=0 to 6 do
begin
read(map[i,j]);
if map[i,j]=0 then break;
end;
x[0]:=-1;
y[0]:=-1;
go(1);
writeln(-1);
close(input);close(output);
end. -
0
2041ms
/*
* =====================================================================================
*
* Filename: a301.cpp
*
* Description:
*
* Version: 1.0
* Created: Monday, 06/02/2014 8:04:35 PM
* Revision: none
* Compiler: gcc
*
* Author: Terry Cheong. (terry182)
* Organization:
*
* =====================================================================================
*/#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxx = 5 + 5, maxy = 7 + 5, maxc = 10 + 5;
int n, c;
int a[maxx][maxy], cnt[maxc];
bool f[maxx][maxy];
int ans[maxx][3];void fall(int x)
{
for (int i = 0; i < 7; i++)
{ if (a[x][i] == 0)
{ int j = i + 1;
while (j < 7 && a[x][j] == 0) j++;
if ( j == 7) return;
else swap(a[x][i], a[x][j]);
}
}
}bool clear()
{
bool flag = false;
for (int i = 0; i < 5; i++)
for (int j = 0; j < 7; j++)
{ if (!a[i][j]) continue;
if ( i < 3 && a[i][j] == a[i+1][j] && a[i][j] == a[i+2][j])
{ f[i][j] = true; f[i+1][j] = true; f[i+2][j] = true;}
if ( j < 5 && a[i][j] == a[i][j+1] && a[i][j] == a[i][j+2])
{ f[i][j] = true; f[i][j+1] = true; f[i][j+2] = true;}
}
for (int i = 0; i < 5; i++)
for (int j = 0; a[i][j] && j < 7; j++)
if (f[i][j])
{
flag = true;
cnt[a[i][j]]--;
a[i][j] = 0;
f[i][j] = 0;
}
for (int i = 0; i < 5; i++)
fall(i);
return flag;
}int check()
{
int minc = 0;
for (int i = 1; i <= c; i++)
if (cnt[i])
if (!minc || minc > cnt[i])
minc = cnt[i];
return minc;
}void print()
{
for (int i = 1; i <= n; i++)
printf("%d %d %d\n", ans[i][0], ans[i][1], ans[i][2]);
exit(0);
}
void dfs(int move)
{int mem[maxx][maxy], memc[maxc];
for (int i = 0; i < 5; i++)
for (int j = 0; j < 7; j++)
mem[i][j] = a[i][j];
for (int i = 1; i <= c; i++)
memc[i] = cnt[i];for (int i = 0; i < 5; i++)
for (int j = 0; a[i][j] && j < 7; j++)
for (int k = 1; k >= -1; k-=2)
if (i+k >= 0 && i+k < 5)
{
if ((k == -1 && a[i-1][j]) || a[i][j] == a[i+k][j]) continue;
ans[move][0] = i; ans[move][1] = j; ans[move][2] = k;
swap(a[i][j], a[i+k][j]);
fall(i); fall(i+k);
while (clear());
int tmp = check();
if (move == n)
{ if (tmp == 0) print();
}
else if (tmp > 2) dfs(move+1);for (int i = 0; i < 5; i++)
for (int j = 0; j < 7; j++)
a[i][j] = mem[i][j];
for (int i = 1; i <= c; i++)
cnt[i] = memc[i];
}}
int main()
{
scanf("%d", &n);
memset(a, 0, sizeof(a));
memset(cnt, 0, sizeof(cnt));
memset(ans, 0, sizeof(ans));
memset(f, 0, sizeof(f));
c = 0;
int tmp;
for (int i = 0; i < 5; i++)
for (int j = 0; j <= 7; j++)
{ scanf("%d", &tmp);
if (tmp == 0)
break;
a[i][j] = tmp;
c = max(c, tmp);
cnt[tmp]++;
}dfs(1);
printf("-1\n");
return 0;
} -
0
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>using namespace std;
#define MAXN 6
#define MAXM 8
#define N 5
#define M 7int n;
int c[MAXN][MAXM];struct map{
int c[MAXN][MAXM];
};void fall(map &m){
for (int i=2;i<=M;i++){
for (int j=0;j++<N;){
if ((!m.c[j][i-1])&&m.c[j][i]){
int k=i;
while (!m.c[j][k-1]){
m.c[j][k-1]=m.c[j][k];
m.c[j][k]=0;
if ((--k)==1) break;
}
}
}
}
}bool DELETE(map &m){
int list[N*M*100][2],rm=0;
for (int i=0;i++<N;){
for (int j=0;j++<M;){
if (i>1&&i<N){
if (m.c[i-1][j]==m.c[i][j]&&m.c[i][j]==m.c[i+1][j]&&m.c[i][j]){
list[++rm][0]=i-1;
list[rm][1]=j;
list[++rm][0]=i;
list[rm][1]=j;
list[++rm][0]=i+1;
list[rm][1]=j;
}
}
if (j>1&&j<M){
if (m.c[i][j-1]==m.c[i][j]&&m.c[i][j]==m.c[i][j+1]&&m.c[i][j]){
list[++rm][0]=i;
list[rm][1]=j-1;
list[++rm][0]=i;
list[rm][1]=j;
list[++rm][0]=i;
list[rm][1]=j+1;
}
}
}
}
for (int i=0;i++<rm;){
m.c[list[i][0]][list[i][1]]=0;
}
if (rm) return true ; else return false;
}void left(int x,int y,map &m){
swap(m.c[x-1][y],m.c[x][y]);
}void right(int x,int y,map &m){
swap(m.c[x][y],m.c[x+1][y]);
}bool flag=false;
bool check(map m){
for (int i=0;i++<N;){
for (int j=0;j++<M;){
if (m.c[i][j]){
return false;
}
}
}
return true;
}int plan[10][3];
void dfs(int x,map m,int q1,int q2,int q3){
if (flag){
return ;
}
if (check(m)){
flag=true;
for (int i=0;i<x;i++){
printf("%d %d %d\n",plan[i][0]-1,plan[i][1]-1,plan[i][2]);
}
return ;
}
if (x>=n){
return ;
}
for (int i=0;i++<N;){
for (int j=0;j++<M;){
if (flag) return ;
if (m.c[i][j]){
if (i<N&&(q1!=i||q2!=j||q3!=1)&&m.c[i][j]!=m.c[i+1][j]){
map u=m;
right(i,j,u);
fall(u);
while (DELETE(u)){
fall(u);
}
plan[x][0]=i;
plan[x][1]=j;
plan[x][2]=1;
dfs(x+1,u,i,j,1);
}
if (i-1&&(q1!=i||q2!=j||q3!=-1)&&m.c[i-1][j]==0){
map u=m;
left(i,j,u);
fall(u);
while (DELETE(u)){
fall(u);
}
plan[x][0]=i;
plan[x][1]=j;
plan[x][2]=-1;
dfs(x+1,u,i,j,-1);
}
} else break;
}
}
}int main(){
scanf("%d",&n);
memset(c,0,sizeof(c));
for (int i=0;i++<N;){
int j=0;
while (1){
int x;
scanf("%d",&x);
if (x){
c[i][++j]=x;
} else break;
}
}
map s;
memset(s.c,0,sizeof(s.c));
for (int i=0;i++<N;){
for (int j=0;j++<M;){
s.c[i][j]=c[i][j];
}
}
dfs(0,s,0,0,0);
if (!flag){
printf("-1\n");
}
return 0;
} -
0
vijos的评测机稍快了点，这不科学。。。
program project1;
const dx:array[1..4] of integer=(0,0,1,-1);
dy:array[1..4] of integer=(1,-1,0,0);
type arr=record
x,y,m:longint;
end;
map=array[1..5,1..7] of longint;
var a:map;
ans:array[1..6]of arr;
v:array[1..5,1..7]of boolean;
n:longint;
{procedure printout;
var i,j:longint;
begin
writeln('***|\**|\**|\**|\**|\**|\|');
for j:=7 downto 1 do begin
for i:=1 to 5 do
write(a,' ');
writeln;
end;
writeln('***|\**|\**|\**|\**|\***|\*|');
end; }
procedure init;
var i,j:longint;
begin
assign(input,'1.in');reset(input);
assign(output,'1.out');rewrite(output);
read(n);
for i:=1 to 5 do
begin
j:=0;
repeat
inc(j);
read(a);
until a=0;
end;
end;
procedure print;
var i:longint;
begin
for i:=1 to n do
begin
writeln(ans[i].x-1,' ',ans[i].y-1,' ',ans[i].m);
end;
halt;
end;
function pd:boolean;
var i:longint;
begin
for i:=1 to 5 do
if a>0 then exit(false);
exit(true);
end;
procedure hengc(i,j:longint);
var tot,k:longint;
begin
tot:=1;
k:=i-1;
while (k>=1)and(a[k,j]=a) do
begin
inc(tot);dec(k);
if tot>=3 then break;
end;
k:=i+1;
while (k=3 then break;
end;
if tot>=3 then
begin
v:=true;k:=j-1;
while (k>=1)and(a[k,j]=a) do
begin
v[k,j]:=true;dec(k);
end;
k:=j+1;
while (k=1)and(a=a) do
begin
inc(tot);dec(k);
if tot>=3 then break;
end;
k:=j+1;
while (k=3 then break;
end;
if tot>=3 then
begin
v:=true;k:=j-1;
while (k>=1)and(a=a) do
begin
v:=true;dec(k);
end;
k:=j+1;
while (k0) do dec(k);
inc(k);
a:=a;
a:=0;
end;
end;
end;
end;
procedure move(x,y,d:longint);
var flag:boolean;temp:longint;
begin
temp:=a[x+d,y];
a[x+d,y]:=a[x,y];
a[x,y]:=temp; // writeln(a[x,y]);writeln(a[x+d,y]);
flag:=true; // down;printout;
while flag do
begin
down;
clear(flag);
end;
end;
procedure dfs(depth:longint);
var i,j:longint;
backup:map;
begin
if depth>n then exit;
for i:=1 to 5 do
for j:=1 to 7 do
backup:=a;
for i:=1 to 5 do
for j:=1 to 7 do
begin
if a=0 then continue;
if (i+1=1)and(a=0) then
begin
ans[depth].x:=i;
ans[depth].y:=j;
ans[depth].m:=-1;
move(i,j,-1);
if pd and (depth=n) then print;
dfs(depth+1);
a:=backup;
end;
end;
end;
procedure main;
begin
dfs(1);
writeln(-1);
close(input);
close(output);
end;
begin
init;
main;
end. -
0
呵呵,时间力压senge
不过我写这题花了不少时间,中间有2个bug,都是因为过程中的变量没初始化,下次要注意了!!!
├ 测试数据 01：答案正确... (0ms, 580KB)
├ 测试数据 02：答案正确... (0ms, 580KB)
├ 测试数据 03：答案正确... (0ms, 580KB)
├ 测试数据 04：答案正确... (0ms, 580KB)
├ 测试数据 05：答案正确... (0ms, 580KB)
├ 测试数据 06：答案正确... (0ms, 580KB)
├ 测试数据 07：答案正确... (0ms, 580KB)
├ 测试数据 08：答案正确... (0ms, 580KB)
├ 测试数据 09：答案正确... (0ms, 580KB)
├ 测试数据 10：答案正确... (309ms, 580KB)
type arr=array[1..5,0..8]of longint;
var
x,y,z:array[1..5]of longint;
c:array[1..6]of arr;
a:arr;
b:array[1..5]of longint;
n:longint;
procedure init;
var i:longint;
begin
readln(n);
for i:=1 to 5 do
begin
while true do
begin
inc(a);
read(a[i,a]);
if a[i,a]=0 then
begin
readln;
dec(a);
break;
end;
end;
end;
end;
procedure deal1(o,s,t,jj,u:longint);
var i,j,z1,z2:longint;
begin
if jj=1 then
begin
for i:=s to t do a:=0;
for i:=s to t do
begin
z1:=0;z2:=0;
for j:=u+1 to a do
if a=o then inc(z1) else break;
for j:=u-1 downto 1 do
if a=o then inc(z2) else break;
if z1+z2>=2 then deal1(o,u-z2,u+z1,2,i);
end;
end else
begin
for j:=s to t do a:=0;
for j:=s to t do
begin
z1:=0;z2:=0;
for i:=u+1 to 5 do
if a=o then inc(z1) else break;
for i:=u-1 downto 1 do
if a=o then inc(z2) else break;
if z1+z2>=2 then deal1(o,u-z2,u+z1,1,j);
end;
end;
end;
procedure handle;
var i,j:longint;
begin
for i:=1 to 5 do begin b[i]:=a;a:=0;end;
for i:=1 to 5 do
begin
for j:=1 to b[i] do
if a0 then
begin
inc(a);
a[i,a]:=a;
end;
for j:=a+1 to b[i] do a:=0;
end;
end;
function deal(k:longint):boolean;
var i,j,u:longint;
begin
for i:=1 to 3 do
for j:=1 to a do
if (ja) then
begin
z[k]:=-1;
inc(a);
a[i-1,a]:=a;
for u:=j to a-1 do a:=a;
a[i,a]:=0;
dec(a);
dfs(k+1);
inc(a);
for u:=a-1 downto j do a:=a;
a:=a[i-1,a];
a[i-1,a]:=0;
dec(a);
end;
end;
a:=c[k];
end;
begin
init;
dfs(1);
writeln(-1);
end. -
0
vijos的评测机真神了。。。裸搜还这么快？
VijosNT Mini 2.0.5.7 Special for Vijos
编译通过...
├ 测试数据 01：答案正确... (0ms, 580KB)
├ 测试数据 02：答案正确... (0ms, 580KB)
├ 测试数据 03：答案正确... (0ms, 580KB)
├ 测试数据 04：答案正确... (0ms, 580KB)
├ 测试数据 05：答案正确... (0ms, 580KB)
├ 测试数据 06：答案正确... (121ms, 580KB)
├ 测试数据 07：答案正确... (840ms, 580KB)
├ 测试数据 08：答案正确... (278ms, 580KB)
├ 测试数据 09：答案正确... (32ms, 580KB)
├ 测试数据 10：答案正确... (1637ms, 580KB)---|---|---|---|---|---|---|---|-
Accepted / 100 / 2910ms / 580KBType
ptype = Record
h: array[0..4] Of longint;
c: array[0..5,0..7] Of longint;
o: array[1..5,1..3] Of longint;
End;Var
n,i,j,tmp: longint;
init: ptype;
Procedure shut;
Begin
halt;
End;
Procedure dfs(dep:longint;now:ptype);
Var
temp: ptype;
i,j,x,y,z,k,move,tmp,last: longint;
Procedure update(Var now:ptype;i,y:longint);Var
j,tmp,last: longint;
Begin
last := y;
For j:=y+1 To now.h[i] Do
If now.c0 Then
Begin
If jlast Then
Begin
tmp := now.c;
now.c := now.c;
now.c := tmp;
End;
last := last+1;
End;
now.h[i] := last-1;
End;
Begin
If dep=3 Then
For z:=last To y-1 Do
now.c[x,z] := -abs(now.c[x,z]);
last := y;
End;
End;
For y:=0 To 6 Do
Begin
last := 0;
For x:=1 To 5 Do
If abs(now.c[x,y])abs(now.c[x-1,y]) Then
Begin
If x-last>=3 Then
For z:=last To x-1 Do
now.c[z,y] := -abs(now.c[z,y]);
last := x;
End;
End;
z := 0;
For x:=0 To 4 Do
Begin
move := -1;
For y:=0 To now.h[x] Do
If now.c[x,y] -
0
裸搜就行，注意每次搜索后要一直处理 消去-掉落 直至没有可以消去的为止
program mayan;
{BY:HT
www.cnblogs.com/htfy}
type
Node=array[1..5,1..7] of byte;
vnode=array[1..5,1..7] of boolean;
rec=record
px,py:byte;
op:boolean//false=-1=left true=1=right
end;
Tcon=array[0..5] of rec;Var
st:node;
stcon:Tcon;
i,o,ct,n:longint;Procedure PrintNode(P:vnode);forward;
Procedure PrintNode(P:node);forward;Procedure fopen;
begin
assign(input,'mayan.in');
assign(output,'mayan.out');
reset(input);
rewrite(output);
end;Procedure fclose;
begin
close(input);
close(output);
end;Function ok(P:node):boolean;
var
i:longint;
begin
for i:=1 to 5 do
if p0 then exit(false);
exit(true);
end;Procedure swap(var a,b:byte);
var
o:longint;
begin
o:=a;a:=b;b:=o;
end;Procedure fall(var p:node);
var
i,j,last:longint;
begin
for i:=1 to 5 do
begin
last:=0;
for j:=1 to 7 do
if p0 then
begin
if last+10 then
st:=o;
end;
end;
{ while puzzle(st) do fall(st);
printnode(st); }
fillchar(stcon,sizeof(stcon),0);
dfs(st,stcon,1);writeln(-1);
end.
-
-1
优化主要是字典序的要求
```
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<set>
#include<vector>
using namespace std;
const int INF = 1000000000;struct order{
int x, y, s;
bool operator == (const order& rhs) const {
return x==rhs.x && y == rhs.y && s == rhs.s;
}
bool operator < (const order& rhs) const {
return (x==rhs.x)? ((y==rhs.y)? ((s == -1)? false:true): y < rhs.y) : x < rhs.x;
}
};
vector<order> way;
vector<order> ans;
int n, x;
int graph[6][8], ge[6][8], color[11];void init(){
cin >> n;
for (int i = 0; i < 5; i++) {
int tot = 0;
while (cin >> x && x) {
color[x]++;
graph[i][tot++] = x;
}
}
}inline vector<order> smler(vector<order> a, vector<order> b) {
for (int i = 0; i < n; i++) {
if (a[i] == b[i]) continue;
if (a[i] < b[i]) return a;
return b;
}
return b;
}int to_clear[6][8]={0}, flag;
void fall(int g[6][8], int col[11]) {
flag = 1;
while (flag){
flag = 0;
for (int i = 0; i < 5; i++)
for (int j = 0; j < 7; j++)
while (j > 0 && g[i][j] && !g[i][j-1]) {//掉落
swap(g[i][j], g[i][j-1]);
j--;
}
for (int i = 0; i < 5; i++)
for (int j = 0; j < 7; j++) if (g[i][j]) {//标记应该消去的
if (g[i][j] == g[i][j+1] && g[i][j+1] == g[i][j+2]) //纵列
to_clear[i][j] = to_clear[i][j+1] = to_clear[i][j+2] = 1;
if (g[i][j] == g[i+1][j] && g[i+1][j] == g[i+2][j]) //横行
to_clear[i][j] = to_clear[i+1][j] = to_clear[i+2][j] = 1;
}
for (int i = 0; i < 5; i++)
for (int j = 0; j < 7; j++) if (to_clear[i][j]) {//消去
col[g[i][j]]--;
g[i][j] = to_clear[i][j] = 0;
flag = 1;
}
}}
int dfs (int g[6][8], int col[11], int cnt) {
fall(g, col);
for (int i = 1; i <= 10; i++) { //某种颜色只剩一种或两种即可判定为死局
if (col[i] == 1 || col[i] == 2) return 0;
}
if (cnt == n) {//做完n步操作后
if (memcmp(g, ge, sizeof(ge)) == 0) {//存在解，更新解
if(ans.size())
ans = smler(ans, way);
else
ans = way;
return 1;
}
return 0;
}
int g1[6][8], col1[11];
for (int i = 0; i < 5; i++)
for (int j = 0; j < 7; j++) {
if (g[i][j]) {
if (i > 0&&!g1[i-1][j]) {//当且仅当左边是空，右边不空的时候
memcpy(col1, col, sizeof(col1));
memcpy(g1, g, sizeof(g1));
swap(g1[i][j], g1[i-1][j]);
way.push_back((order){i, j, -1});
if(dfs(g1, col1, cnt+1)) return 1;//如果当前ij对应有解，则不用考虑之后的，因为字典序会变大
way.pop_back();
}
if (i < 4) {
memcpy(col1, col, sizeof(col1));
memcpy(g1, g, sizeof(g1));
swap(g1[i][j], g1[i+1][j]);
way.push_back((order){i, j, 1});
if(dfs(g1, col1, cnt+1)) return 1;
way.pop_back();
swap(g1[i][j], g1[i+1][j]);
}
}
}
return 0;
}int main(){
//freopen ( "in.txt" , "r" , stdin);
init();
dfs(graph, color, 0);
if (ans.size())
for (int i = 0; i < ans.size(); i++)
cout << ans[i].x << " " << ans[i].y << " " << ans[i].s << "\n";
else cout << "-1";
return 0;
}
``` -
-1
#include <cstdio>
#include <cstring>int st[5][7]={0};
int maxstep,rich=0;void init(){
scanf("%d",&maxstep);
for(int i=0;i<5;i++)
for(int j=0;j<=7;j++){ //这里是等于
scanf("%d",&st[i][j]);
if(st[i][j]==0)
break;
}
}int fall(int p[5][7]){
int temp[7],n,flag,last[5][7];
memcpy(last,p,sizeof(last));
for(int i=0;i<5;i++){
n=0;
memset(temp,0,sizeof(temp));
for(int j=0;j<7;j++){
if(p[i][j]!=0)
temp[n++]=p[i][j];}
for(int j=0;j<7;j++)
p[i][j]=temp[j];
}
flag=memcmp(last,p,sizeof(last));
if(flag!=0)
flag=1;
return flag;
}void merge(int p[5][7]){
int n;
int chg[5][7]={0};
for(int i=0;i<5;i++){
n=1;
for(int j=1;j<=7;j++){
if(j==7)
goto q1;
if(p[i][j]==0)
goto q1;if(p[i][j]==p[i][j-1])
n++;
else
q1: if(n>=3){
for(int k=1;k<=n;k++)
chg[i][j-k]=1;
n=1;
}
else
n=1;
}
}
for(int j=0;j<7;j++){
n=1;
for(int i=1;i<=5;i++){
if(i==5)
goto q2;
if(p[i][j]==0)
goto q2;if(p[i][j]==p[i-1][j]){
n++;
}
else
q2: if(n>=3){
for(int k=1;k<=n;k++)
chg[i-k][j]=1;
n=1;
}
else
n=1;
}
}
for(int i=0;i<5;i++)
for(int j=0;j<7;j++)
if(chg[i][j]==1)
p[i][j]=0;
int q=fall(p);
if(q)
merge(p);
}int judge(int p[5][7]){
int flag=1;
for(int i=0;i<5;i++)
for(int j=0;j<7;j++)
flag*=p[i][j]==0;
return flag;
}struct way{
int x,y,z;
}path[10];
int u=0;void move(int p[5][7],way a){
int i=a.x,j=a.y,k=a.z;
int temp=p[i][j];
p[i][j]=p[i+k][j];
p[i+k][j]=temp;
fall(p);
}/*
为0就跳过
不为0：
左边界右移
右边界，如果左边为0，左移
中间，右移。如果左边为0，再左移
*/int dfs(int p[5][7],int step){
if(step==maxstep)
if(judge(p))
return 1;
else
return 0;
int temp[5][7];
way a;
int q[2],w;
for(int i=0;i<5;i++)
for(int j=0;j<7;j++){
if(p[i][j]==0)
continue;
a.x=i,a.y=j;if(i==2&&j==0&&step==0)
int wewq=213;if(i==0)
q[0]=1,w=1;
if(i==4){
if(p[i-1][j]==0)
q[0]=-1,w=1;
else
continue;
}
if(i>0&&i<4){
q[0]=1,w=1;
if(p[i-1][j]==0)
q[1]=-1,w=2;
}
for(int k=0;k<w;k++){
memcpy(temp,p,sizeof(temp));
a.z=q[k];
move(temp,a);
merge(temp);
if(dfs(temp,step+1)==1){
path[u].x=a.x;
path[u].y=a.y;
path[u].z=a.z;
u++;
return 1;
}
}
}return 0;
}int main(){
init();
dfs(st,0);
for(int i=u-1;i>=0;i--){
printf("%d %d %d",path[i].x,path[i].y,path[i].z);
printf("\n");
}
if(u==0)
printf("-1");
return 0;
} -
-1
自己进步还是很快的
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int map[10][10],Lim;
struct Data{
int x,y,to;
Data(int x_=0,int y_=0,int to_=0){
x=x_;y=y_;to=to_;
}
}ans[6];void Debug(int m[10][10]){
printf("~~~~~~~~~~~\n");
for(int y=7;y>=1;y--){
for(int x=1;x<=5;x++)
printf("%d ",m[x][y]);
printf("\n");
}
printf("~~~~~~~~~~~\n");
}void Grav(int m[10][10]){
for(int x=1;x<=5;x++)
for(int y=2;y<=7;y++){
int j=y;
while(j>1&&m[x][j]&&!m[x][j-1])
swap(m[x][j],m[x][j-1]),j--;
}
}bool Clear(int m[10][10]){
bool flag[10][10];
memset(flag,false,sizeof(flag));
for(int x=1;x<=5;x++){
for(int y=1;y<=7;y++){
if(!m[x][y])continue;
int w;
for(w=1;y+w<=7;w++)
if(m[x][y+w]!=m[x][y+w-1])
break;
if(w>=3){
for(int v=0;v<w;v++)
flag[x][y+v]=true;
}for(w=1;y-w>=1;w++)
if(m[x][y-w]!=m[x][y-w+1])
break;
if(w>=3){
for(int v=0;v<w;v++)
flag[x][y-v]=true;
}for(w=1;x+w<=5;w++)
if(m[x+w][y]!=m[x+w-1][y])
break;
if(w>=3){
for(int v=0;v<w;v++)
flag[x+v][y]=true;
}for(w=1;x-w>=1;w++)
if(m[x-w][y]!=m[x-w+1][y])
break;
if(w>=3){
for(int v=0;v<w;v++)
flag[x-v][y]=true;
}
}
}for(int x=1;x<=5;x++)
for(int y=1;y<=7;y++)
if(flag[x][y]){
m[x][y]=0;
flag[0][0]=true;
}
return flag[0][0];
}bool IS_OK(int m[10][10]){
for(int x=1;x<=5;x++)
if(m[x][1])
return false;
return true;
}void Copy(int to[10][10],int m[10][10]){
for(int x=1;x<=5;x++)
for(int y=1;y<=7;y++)
to[x][y]=m[x][y];
}bool Solve(int m[10][10],int dep){
if(IS_OK(m)){
if(dep==Lim)
return true;
else
return false;
}
if(dep==Lim)
return false;
int now[10][10];
for(int x=1;x<=5;x++){
for(int y=1;y<=7;y++){
if(!m[x][y])continue;
if(x+1<=5){
Copy(now,m);
swap(now[x][y],now[x+1][y]);
Grav(now);
while(Clear(now))
Grav(now);
ans[dep+1]=Data(x,y,1);
if(Solve(now,dep+1))
return true;
}
if(x-1>=1&&!m[x-1][y]){
Copy(now,m);
swap(now[x][y],now[x-1][y]);
Grav(now);
while(Clear(now))
Grav(now);
ans[dep+1]=Data(x,y,-1);
if(Solve(now,dep+1))
return true;
}
}
}
return false;
}void Print(){
for(int i=1;i<=Lim;i++)
printf("%d %d %d\n",ans[i].x-1,ans[i].y-1,ans[i].to);
}int main(){
freopen("mayan.in","r",stdin);
freopen("mayan.out","w",stdout);
scanf("%d",&Lim);for(int i=1,j;i<=5;i++){
scanf("%d",&map[i][j=1]);
while(map[i][j])
scanf("%d",&map[i][++j]);
}
if(Solve(map,0))
Print();
else
printf("-1\n");
return 0;
}
Sky1231 (sky1231)
LV 10
@ 2017-08-14 11:46:33
- 1
