3 条题解

  • 1
    @ 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;
    }
    
    • 1
      @ 2021-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;
      }
      
      • 0
        @ 2023-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
        上传者