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;
}