3 条题解
-
1许致远___ (gzxzy0505) LV 4 @ 2022-8-5 19:06:55
#include<cstdio> #include<iostream> #include<cstring> #define INF 536870912 using namespace std; char map[6][6]; char check[6][6]={ '0','0','0','0','0','0', '0','1','1','1','1','1', '0','0','1','1','1','1', '0','0','0','*','1','1', '0','0','0','0','0','1', '0','0','0','0','0','0', }; int xm[9]={0,-2,-2,-1,-1,1,1,2,2}; int ym[9]={0,-1,1,-2,2,-2,2,-1,1}; int ans; inline void swap(char &p1,char &p2){ char mid=p1; p1=p2; p2=mid; } inline int dif(){ int ret=0; for(int i=1;i<=5;i++){ for(int j=1;j<=5;j++){ if(map[i][j]!=check[i][j]) ret++; } } return ret; } inline void dfs(int x,int y,int d,int f){ int l=dif(); if(d+l>16) return ; if(d>=ans) return ; if(l==0){ ans=d; return ; } for(int i=1;i<=8;i++){ if((x+xm[i]<1)||(x+xm[i]>5)) continue; if((y+ym[i]<1)||(y+ym[i]>5)) continue; if(f+i!=9){ swap(map[y+ym[i]][x+xm[i]],map[y][x]); dfs(x+xm[i],y+ym[i],d+1,i); swap(map[y+ym[i]][x+xm[i]],map[y][x]); } } } inline void init(){ int x,y; for(int i=1;i<=5;i++) cin>>map[i]+1; for(int i=1;i<=5;i++){ for(int j=1;j<=5;j++){ if(map[i][j]=='*') { x=j; y=i; } } } ans=25; dfs(x,y,0,0); printf("%d\n",ans==25?-1:ans); } int main(){ int t; scanf("%d",&t); while(t--)init(); return 0; }
-
12021-8-7 21:15:26@
C++ :
/* date : 2019-07-27 12:37:13 problem ID : problem WEB : */ #include <iostream> #include <string.h> #include <cstdio> #include <algorithm> using namespace std; #define LL long long int ans = -1 , nowa , nowb , d; int p[8] = {-2 , -2 , -1 , -1 , 1 , 1 , 2 , 2}; int q[8] = {-1 , 1 , -2 , 2 , -2 , 2 , -1 , 1}; int a[6][6] , goal[6][6]={{0,0,0,0,0,0}, {0,1,1,1,1,1}, {0,0,1,1,1,1}, {0,0,0,-1,1,1}, {0,0,0,0,0,1}, {0,0,0,0,0,0}}; void putin() { char x; for (int i = 1 ; i < 6 ; i++) for (int j = 1 ; j < 6 ; j++) { cin >> x; if (x == '*') { a[i][j] = -1; nowa = i; nowb = j; } else a[i][j] = x - '0'; } } int flag() { int ans = 0; for (int i = 1 ; i < 6 ; i++) for (int j = 1 ; j < 6 ; j++) if (a[i][j] != goal[i][j]) ans++; return ans; } bool dfs(int x , int y , int step) { if (step > d) return false; int z = flag(); if (z == 0) { ans = step; return true; } if (z + step > d + 1) return false; int xx = x , yy = y; for (int i = 0 ; i < 8 ; i++) { xx = x + p[i]; yy = y + q[i]; if (xx > 0 && xx < 6 && yy > 0 && yy < 6) { swap(a[x][y] , a[xx][yy]); if (dfs(xx , yy , step + 1)) return 1; swap(a[x][y] , a[xx][yy]); } } return 0; } int main() { int n; cin >> n; for (int i = 1 ; i <= n ; i++) { bool fl = 0; putin(); ans = -1; int sum = flag(); for (d = sum ; d <= 15 ; d++) { if (dfs(nowa , nowb , 0)) { cout << ans << endl; fl = 1; break; } } if (!fl) cout << -1 << endl; } return 0; }
-
02023-1-13 9:58:02@
/********************************* 备注: *********************************/ #include<map> #include<list> #include<stack> #include<queue> #include<cmath> #include<queue> #include<stack> #include<deque> #include<math.h> #include<cstdio> #include<string> #include<vector> #include<cstring> #include<fstream> #include<stdio.h> #include<sstream> #include<iomanip> #include<iostream> #include<string.h> #include<algorithm> #include<bits/stdc++.h> using namespace std; #define in int #define ch char #define lo long #define fl float #define sh short #define ld long double #define lli long long int #define db double #define str string #define ll long long const int N =1e6+10; const int INF =0x3f3f3f3f; int read() { int f=1,x=0; char ss=getchar(); while(ss<'0'||ss>'9'){if(ss=='-')f=-1;ss=getchar();} while(ss>='0'&&ss<='9'){x=x*10+ss-'0';ss=getchar();} return f*x; } int n; int ans[6][6]= {{0,0,0,0,0,0}, {0,1,1,1,1,1}, {0,0,1,1,1,1}, {0,0,0,2,1,1}, {0,0,0,0,0,1}, {0,0,0,0,0,0}}; int nxtx[]={1,1,2,2,-2,-2,-1,-1}; int nxty[]={2,-2,1,-1,1,-1,2,-2}; int a[10][10],k; int judge; int check() { for(int i=1;i<=5;++i) for(int j=1;j<=5;++j) if(ans[i][j]!=a[i][j])return 0; return 1; } int test(int step) { int cnt=0; for(int i=1;i<=5;++i) for(int j=1;j<=5;++j) if(ans[i][j]!=a[i][j]){ if(++cnt+step>k) return 0;} return 1; } void A_star(int step,int x,int y,int pre) { if(step==k){ if(check())judge=1; return;} if(judge) return; for(int i=0;i<8;++i) { int nx=x+nxtx[i],ny=y+nxty[i]; if(nx<1||nx>5||ny<1||ny>5||i+pre==7) continue; swap(a[x][y],a[nx][ny]); if(test(step)&&!judge) A_star(step+1,nx,ny,i); swap(a[x][y],a[nx][ny]); } } int main() { n=read(); while(n--) { int x,y; judge=0; for(int i=1;i<=5;++i) { char ss[7]; scanf("%s",&ss); for(int j=0;j<5;++j) if(ss[j]=='*') a[i][j+1]=2,x=i,y=j+1; else a[i][j+1]=ss[j]-'0'; } for(k=1;k<=15;++k) { A_star(0,x,y,-1); if(judge) { printf("%d\n",k); break;} } if(!judge)cout<<"-1"<<endl; } return 0; }
- 1
信息
- ID
- 106
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 1
- 标签
- 递交数
- 54
- 已通过
- 43
- 上传者