P2324-[SCOI2005]骑士精神

今天药忘吃喽~ 2023-06-01 08:58 13阅读 0赞

1 #include <bits/stdc++.h>
      2 #define _for(i,a,b) for(int i = (a);i < b;i ++)
      3 #define _rep(i,a,b) for(int i = (a);i > b;i --)
      4 #define INF 0x3f3f3f3f
      5 #define MOD 1000000007
      6 #define maxn 10
      7 typedef long long ll;
      8 using namespace std;
      9 
     10 inline ll read()
     11 {
     12     ll ans = 0;
     13     char ch = getchar(), last = ' ';
     14     while(!isdigit(ch)) last = ch, ch = getchar();
     15     while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
     16     if(last == '-') ans = -ans;
     17     return ans;
     18 }
     19 inline void write(ll x)
     20 {
     21     if(x < 0) x = -x, putchar('-');
     22     if(x >= 10) write(x / 10);
     23     putchar(x % 10 + '0');
     24 }
     25 int T;
     26 int mp[maxn][maxn];
     27 int bx,by;
     28 const int dx[]={
        1,1,-1,-1,2,2,-2,-2};
     29 const int dy[]={
        2,-2,2,-2,1,-1,1,-1};
     30 const int target[maxn][maxn] =
     31 {
     32     {
        0,0,0,0,0,0},
     33     {
        0,2,2,2,2,2},
     34     {
        0,1,2,2,2,2},
     35     {
        0,1,1,0,2,2},
     36     {
        0,1,1,1,1,2},
     37     {
        0,1,1,1,1,1}
     38 };
     39 
     40 int g()
     41 {
     42     int rnt = 0;
     43     _for(i,1,6)
     44         _for(j,1,6)
     45         {
     46             if(!mp[i][j]) continue;
     47             if(target[i][j] != mp[i][j])
     48                 rnt ++;
     49         }
     50     return rnt;
     51 }
     52 bool valid(int x,int y)
     53 {    return x>=1&&x<6&&y>=1&&y<6;}
     54 bool dfs(int maxstep,int step)
     55 {
     56     int gg = g();
     57     if(!gg)
     58         return true;
     59     if(step+gg>maxstep)
     60         return false;
     61     _for(i,0,8)
     62     {
     63         int nx = bx+dx[i];
     64         int ny = by+dy[i];
     65         if(valid(nx,ny))
     66         {
     67             int tx = bx,ty = by;
     68             swap(mp[bx][by],mp[nx][ny]);
     69             bx = nx,by = ny;
     70             if(dfs(maxstep,step+1)) return true;
     71             bx = tx,by = ty;
     72             swap(mp[nx][ny],mp[bx][by]);
     73         }
     74     }
     75     return false;
     76 }
     77 int main()
     78 {
     79     T = read();
     80     while(T--)
     81     {
     82         char tmp;
     83         _for(i,1,6)
     84         _for(j,1,6)
     85         {
     86             scanf(" %c",&tmp);
     87             if(tmp=='*')
     88                 mp[i][j] = 0,bx = i,by = j;
     89             else
     90                 mp[i][j] = tmp-'0'+1;
     91         }
     92         int flag = 0;
     93         
     94         _for(maxstep,0,16)
     95         {
     96             if(dfs(maxstep,0))
     97             {    flag = 1,printf("%d\n",maxstep);break;}
     98         }
     99         if(!flag)
    100             printf("%d\n",-1);
    101     }
    102     return 0;
    103 }

转载于:https://www.cnblogs.com/Asurudo/p/11616905.html