2 条题解
-
1
#include<bits/stdc++.h> #define ll long long #define rg register using namespace std; int read(){ int x = 0,f = 1; char c = getchar(); while(c < '0'||c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') {x = x*10 + c - '0'; c = getchar();} return x*f; } struct Ans{ int x, y, d; }ans[6]; int n, k, mp[6][8], fag, last[6][6][8], Step;//mp[i][j]: x = i, y = j; 起始从(1, 1)开始,按照数学坐标系模拟 bool res[6][8]; void down() {//掉落 for (int i = 1; i <= 5; i++) { int x = 0; for (int j = 1; j <= 7; j++) { if (!mp[i][j]) x++; else { if (x == 0) continue; mp[i][j - x] = mp[i][j], mp[i][j] = 0; } } } } bool delet() {//消除操作 int flag = 0; for (int i = 1; i <= 5; i++) { for (int j = 1; j <= 7; j++) { if (i - 1 >= 1 && i + 1 <= 5 && mp[i - 1][j] == mp[i][j] && mp[i + 1][j] == mp[i][j] && mp[i][j]) { res[i - 1][j] = 1, res[i][j] = 1, res[i + 1][j] = 1, flag = 1; } if(j - 1 >= 1 && j + 1 <= 7 && mp[i][j - 1] == mp[i][j] && mp[i][j] == mp[i][j + 1] && mp[i][j]) { res[i][j] = 1, res[i][j - 1] = 1, res[i][j + 1] = 1, flag = 1; } } } if (flag == 0) return false; for (int i = 1; i <= 5; i++) { for (int j = 1; j <= 7; j++) { if (res[i][j]) mp[i][j] = 0, res[i][j] = 0; } } return true; } void move(int x, int y, int d) { swap(mp[x][y], mp[x + d][y]); down(); while(delet()) down();//连续消 } bool check() { for (int i = 1; i <= 5; i++) if (mp[i][1]) return 0; return 1; } void copy(int x) { for (int i = 1; i <= 5; i++) { for (int j = 1; j <= 7; j++) { last[x][i][j] = mp[i][j]; } } } void dfs(int step) { if (check()) { for (int i = 1; i <= n; i++) { printf("%d %d %d\n", ans[i].x, ans[i].y, ans[i].d); } exit(0); } if (step == n + 1) return ;//超步数 copy(step); for (int i = 1; i <= 5; i++) { for (int j = 1; j <= 7; j++) { if (mp[i][j]) { if (i + 1 <= 5 && mp[i][j] != mp[i + 1][j]){//右侧没有方块 move(i, j, 1); ans[step].x = i - 1, ans[step].y = j - 1, ans[step].d = 1; dfs(step + 1); for (int i = 1; i <= 5; i++) { for (int j = 1; j <= 7; j++) { mp[i][j] = last[step][i][j]; } } ans[step].x = -1, ans[step].y = -1, ans[step].d = -1; } if (i - 1 >= 1 && mp[i - 1][j] == 0) { move(i, j, -1); ans[step].x = i - 1, ans[step].y = j - 1, ans[step].d = -1; dfs(step + 1); for (int i = 1; i <= 5; i++) { for (int j = 1; j <= 7; j++) { mp[i][j] = last[step][i][j]; } } ans[step].x = -1, ans[step].y = -1, ans[step].d = -1; } } } } } int main(){ n = read(); memset(ans, -1, sizeof ans); for (int i = 1, tot, x; i <= 5; i++) { x = read(), tot = 1; while(x) {mp[i][tot++] = x, x = read();} } dfs(1); puts("-1"); return 0; }
-
0
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cctype> #include<cstdlib> #define ll long long #define N 10 using namespace std; int read() { int X=0,w=0; char ch=0; while(!isdigit(ch)) {w|=ch=='-';ch=getchar();} while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X; } int n,map[N][N],ans[N][5],last[N][N][N],xiao[N][N]; bool remove(){ int flag=0; for(int i=1;i<=5;i++) for(int j=1;j<=7;j++){ if(i-1>=1&&i+1<=5&&map[i][j]==map[i-1][j]&&map[i][j]==map[i+1][j]&&map[i][j]){ xiao[i-1][j]=1;xiao[i+1][j]=1;xiao[i][j]=1;flag=1; } if(j-1>=1&&j+1<=7&&map[i][j]==map[i][j+1]&&map[i][j]==map[i][j-1]&&map[i][j]){ xiao[i][j]=1;xiao[i][j+1]=1;xiao[i][j-1]=1;flag=1; } } if(!flag)return 0; for(int i=1;i<=5;i++) for(int j=1;j<=7;j++) if(xiao[i][j]){ xiao[i][j]=0; map[i][j]=0; } return 1; } bool check(){ for(int i=1;i<=5;i++) if(map[i][1])return 0; return 1; } void copy(int x){ for(int i=1;i<=5;i++) for(int j=1;j<=7;j++) last[x][i][j]=map[i][j]; } void update(){ for(int i=1;i<=5;i++){ int wow=0; for(int j=1;j<=7;j++){ if(!map[i][j])wow++; else{ if(!wow)continue; map[i][j-wow]=map[i][j]; map[i][j]=0; } } } } void move(int i,int j,int x){ int tmp=map[i][j]; map[i][j]=map[i+x][j]; map[i+x][j]=tmp; update(); while(remove())update(); } void dfs(int x){ if(check()){ for(int i=1;i<=n;i++){ if(i!=1)printf("\n"); for(int j=1;j<=3;j++) printf("%d ",ans[i][j]); } exit(0); } if(x==n+1)return; copy(x); for(int i=1;i<=5;i++) for(int j=1;j<=7;j++){ if(map[i][j]){ if(i+1<=5&&map[i][j]!=map[i+1][j]){ move(i,j,1); ans[x][1]=i-1;ans[x][2]=j-1;ans[x][3]=1; dfs(x+1); for(int i=1;i<=5;i++) for(int j=1;j<=7;j++) map[i][j]=last[x][i][j]; ans[x][1]=-1;ans[x][2]=-1;ans[x][3]=-1; } if(i-1>=1&&map[i-1][j]==0){ move(i,j,-1); ans[x][1]=i-1;ans[x][2]=j-1;ans[x][3]=-1; dfs(x+1); for(int i=1;i<=5;i++) for(int j=1;j<=7;j++) map[i][j]=last[x][i][j]; ans[x][1]=-1;ans[x][2]=-1;ans[x][3]=-1; } } } } int main() { // freopen("Manya.in","r",stdin); // freopen("Manya.out","w",stdout); n=read(); for(int i=1;i<=5;i++){ for(int j=1;j<=8;j++){ int x=read(); if(x==0)break; map[i][j]=x; } } memset(ans,-1,sizeof(ans)); dfs(1); puts("-1"); return 0; }
- 1
信息
- ID
- 313
- 时间
- 3000ms
- 内存
- 128MiB
- 难度
- 5
- 标签
- 递交数
- 15
- 已通过
- 5
- 上传者