题解

20 条题解

  • 2
    @ 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);
        }
    }
    
  • 1
    @ 2016-11-01 13:32:17
    #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
    @ 2016-10-30 22:03:38

    难道说数据中存在操作为4 x 1这样的东西吗。。交了N次都是WA,后来把(i<=4)的一个条件去掉就AC了。。不过也有可能是我自己写错了。。

    注意:1.题目中的n是最大步数,而不是要求恰好n步。
    2.由于左边的数右移是和右边的数左移等价的,所以可以在这里剪枝
    3.当一种颜色的方块只有1个或2个时,肯定无法消除,所以剪枝
    ps:memcpy真好用

  • 0
    @ 2016-10-11 21:41:52

    千万要注意读入!!!!!!!!!

    #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
    @ 2016-08-19 11:24:03

    优化主要是字典序的要求
    ```
    #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;
    }
    ```

  • 0
    @ 2016-07-19 09:29:17

    #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;
    }

  • 0
    @ 2016-04-08 14:38:08

    自己进步还是很快的
    #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;
    }

  • 0
    @ 2014-11-27 21:19:02

    这么长的代码我也是醉了- -没人为了多个20分写那么长的一层吧- -坑爹

  • 0
    @ 2014-11-07 20:02:51

    //代码风格很诡异……

    //剪枝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
    @ 2014-10-30 17:59:27

    只对了30%就是那个1层的

    后面都超时了,想测也测不了,求解应该要怎么搜啊?

  • 0
    @ 2014-10-26 00:42:40

    测试数据 #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
    @ 2014-10-25 22:44:20

    #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
    @ 2014-10-10 11:13:49

    求各位大大们看一下哪里错了,好像是死循环了但是用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
    @ 2014-06-18 17:42:36

    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
    @ 2013-09-19 17:47:01

    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <cstdlib>

    using namespace std;

    #define MAXN 6
    #define MAXM 8
    #define N 5
    #define M 7

    int 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
    @ 2012-11-05 00:16:26

    一开始超时了,后来才想到假设有相邻的两个颜色不同的方块,如果搜了左边的向右移,就不用搜右边的向左移了。

  • 0
    @ 2012-11-03 11:23:51

    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
    @ 2012-10-18 20:28:34

    呵呵,时间力压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
    @ 2012-10-17 20:48:52

    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 / 580KB

    Type

    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
    @ 2012-10-10 20:15:03

    裸搜就行,注意每次搜索后要一直处理 消去-掉落 直至没有可以消去的为止

    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

信息

ID
1738
难度
7
分类
搜索 点击显示
标签
递交数
2083
已通过
459
通过率
22%
被复制
9
上传者