20pts 求调
查看原帖
20pts 求调
1359837
Dream_Stars楼主2025/1/23 12:37

rt,样例第二组数据 TLE,不知为什么。

我已经把代码改成和 tj 相似(同)的形式了,还是在第二组数据 TLE。

所以求调:

# include <bits/stdc++.h>

# define up(i ,x ,y) for (register int i = x ; i <= y; i ++)

using namespace std;

inline int read(){int s = 0 , w = 0;char c = getchar();while(!isdigit(c)){w |= (c == '-');c = getchar();}while(isdigit(c)){s = (s << 1) + (s << 3) + (c ^ 48);c = getchar();}return w ? -s : s;}
inline void write(int x){if(x < 0) putchar('-') , x = -x;if(x > 9) write(x / 10);putchar(x % 10 | 48);}
inline void writesp(int x){write(x) , putchar(' ');}
inline void writeln(int x){write(x) , putchar('\n');}

const int result[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}

} ;

int a[6][6] ,b[6][6];
bool f;
const int fx[8] = {-1 ,-2 ,-2 ,-1 ,1 ,2 ,2 ,1} ,fy[8] = {-2 ,-1 ,1 ,2 ,2 ,1 ,-1 ,-2};

inline bool check (){
  int sum = 0;
  up (i ,1 ,5) up (j ,1, 5) sum += (a[i][j] != result[i][j]);
  return sum;
} inline bool In_Range (int ax ,int ay){
  return ax >= 1 && ay >= 1 && ax <= 5 && ay <= 5;
} inline void dfs (int dep ,int x ,int y ,int mx_dep){
  
  if (f) return ;
  
  int cnt = check ();

  if (dep == mx_dep) {if (!cnt) f = 1 ; return ;}

  up (i ,0 ,7){
    
    int ax = fx[i] + x ,ay = fy[i] + y;
    
    if (!In_Range (ax ,ay)) continue;
    
    swap (a[x][y] ,a[ax][ay]);
    
    int cnt = check ();

    if (dep + cnt <= mx_dep) dfs (dep + 1 ,ax, ay ,mx_dep);

    swap (a[x][y] ,a[ax][ay]);
  }

} inline void solve (){

  f = 0;
  
  int sx = 0, sy = 0;

  up (i ,1 ,5) up (j ,1 ,5){
    char x;
    cin >> x;
    if (isdigit (x)) a[i][j] = x - 48;
    else a[i][j] = -1 ,sx = i ,sy = j;
    b[i][j] = a[i][j];
  }
//writesp (sx) ,writeln (sy);
  up (dep ,1 ,15){
    dfs (0 ,sx ,sy ,dep);
    up (i ,1, 5) up(j ,1, 5) a[i][j] = b[i][j];
    if (f) {writeln (dep) ; break;}
  } if (!f) puts("-1");
} signed main (){
  int T = read ();
  while (T --) solve (); 
  return 0;
}

2025/1/23 12:37
加载中...