TLE
#include <iostream>
#include <cstring>
#include <algorithm>
#include<queue>
using namespace std;
int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};
string st,ed;
int f(string s)//启发函数
{
int cnt = 0;
for(int i = 0; i < s.size(); i ++)
if(s[i] != '*' && s[i] != ed[i])cnt ++;
return cnt;
}
bool check(string s)
{
for(int i = 0; i < s.size(); i ++)
if(s[i] != ed[i])return false;
return true;
}
bool dfs(int u,int max_depth,string s)
{
if(u + f(s) > max_depth)return false;
if(check(s))return true;
int k = s.find('*');
for(int i = 0; i < 8; i ++)
{
//二维坐标变换,一维移动
int x = k / 5 + dx[i],y = k % 5 + dy[i];
if(x < 0 || x >= 5 || y < 0 || y >= 5)continue;
swap(s[x * 5 + y],s[k]);
if(dfs(u + 1,max_depth,s)) return true;
swap(s[x * 5 + y],s[k]);
}
//无解
return false;
}
int main()
{
int t;cin >> t;
while(t --)
{
st = "";
for(int i = 0; i < 5; i ++)
for(int j = 0; j < 5; j ++)
{
char c;cin >> c;
st += c;
}
ed = "111110111100*110000100000";
int depth = 0;
while(depth <= 15 && !dfs(0,depth,st))depth ++;
if(depth > 15)cout << -1 << endl;
else cout << depth << endl;
}
return 0;
}
数组模拟
#include <iostream>
#include <cstring>
#include <algorithm>
#include<queue>
using namespace std;
int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};
int a[6][6];
int b[6][6] =
{
{1,1,1,1,1},
{0,1,1,1,1},
{0,0,-1,1,1},
{0,0,0,0,1},
{0,0,0,0,0}
};
int f()//启发函数
{
int cnt = 0;
for(int i = 0; i < 5; i ++)
for(int j = 0; j < 5; j ++)
{
if(a[i][j] != -1 && a[i][j] != b[i][j])
cnt ++;
}
return cnt;
}
bool check()
{
for(int i = 0; i < 5;i ++)
{
for(int j =0; j < 5; j ++)
{
if(a[i][j] != b[i][j])
return false;
}
}
return true;
}
bool dfs(int u,int max_depth,int sx,int sy)
{
if(u + f() > max_depth)return false;
if(check())return true;
for(int i = 0; i < 8; i ++)
{
int x = sx + dx[i],y = sy + dy[i];
if(x < 0 || x >= 5 || y < 0 || y >= 5)continue;
swap(a[x][y],a[sx][sy]);
if(dfs(u + 1,max_depth,x,y))return true;
swap(a[x][y],a[sx][sy]);
}
//无解
return false;
}
int main()
{
int t;cin >> t;
while(t --)
{
int sx,sy;
for(int i = 0; i < 5; i ++)
for(int j = 0; j < 5; j ++)
{
char c;cin >> c;
if(c == '1')a[i][j] = 1;
else if(c == '0')a[i][j] = 0;
else
{
a[i][j] = -1;
sx = i,sy = j;
}
}
int depth = 0;
while(depth <= 15 && !dfs(0,depth,sx,sy))depth ++;
if(depth > 15)cout << -1 << endl;
else cout << depth << endl;
}
return 0;
}