题目链接：https://vjudge.net/problem/Gym-100783E
跟上一题有点像：但是还是有所不同，这也是觉得自己傻的地方：上一题只要有一个到目标点就可以，所以可以直接变图（swap），不会改变目标点的位置，因为有一个到目标点就直接标记return了，可是这里要是变图（swap），会把目标点的位置改变，因为这里必须是'1'到目标点，可是如果'2'，'3'，‘4’到目标点的话，会与目标点交换，这时就改变了目标点的位置
WA：
1 #include <bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 const int maxn = 2e5+10;
5 const int inf=0x3f3f3f3f;
6 #define lowbit(x) ((x)&(-x))
7 #define rep(i,first,last) for(int i=first;i<=last;i++)
8 #define dep(i,first,last) for(int i=first;i>=last;i--)
9
10 int ok,w,h,l,n,minn;
11 char g[15][15];
12 int dix[4]={0,0,1,-1};
13 int diy[4]={1,-1,0,0};
14
15 void check(int &x,int &y,int dx,int dy){
16 int nx=x+dx,ny=y+dy;
17 while( nx>=1&&nx<=h&&ny>=1&&ny<=w&&(g[nx][ny]=='.'||g[nx][ny]=='X')){
18 x=nx,y=ny;
19 nx+=dx;
20 ny+=dy;
21 }
22 }
23
24 void dfs(int step){
25 if( step>l || step>minn) return;
26 int x,y;
27 rep(i,1,h){
28 rep(j,1,w){
29 if( g[i][j]>='1'&&g[i][j]<='4'){
30 rep(k,0,3){
31 x=i;y=j;
32 check(x,y,dix[k],diy[k]);
33 if( g[x][y]=='X'&&g[i][j]=='1'){
34 ok=1;
35 minn=min(minn,step);
36 }
37 if( i==x&&j==y ) continue;
38 swap(g[i][j],g[x][y]);
39 dfs(step+1);
40 swap(g[i][j],g[x][y]);
41 }
42 }
43 }
44 }
45 }
46 int main()
47 {
48 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
49 minn=inf;
50 cin>>n>>w>>h>>l;
51 rep(i,1,h){
52 rep(j,1,w){
53 cin>>g[i][j];
54 }
55 }
56
57 dfs(1);
58 // if( h==1 && w==1 && g[1][1]=='1' ) printf("0\n");
59 if( !ok ) printf("NO SOLUTION\n");
60 else printf("%d\n",minn);
61 return 0;
62 }
WA4
要想不TLE，还要用到哈希判当前状态是否走过
AC:
1 #include <bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 const int maxn = 2e5+10;
5 const int inf=0x3f3f3f3f;
6 #define lowbit(x) ((x)&(-x))
7 #define rep(i,first,last) for(int i=first;i<=last;i++)
8 #define dep(i,first,last) for(int i=first;i>=last;i--)
9
10 struct node{
11 int x,y;
12 }a[6];
13 char g[15][15];
14 int dix[4]={0,0,1,-1};
15 int diy[4]={1,-1,0,0};
16 int vis[15][15];
17 unordered_map<int,int>mp;
18 int n,h,w,l,minn;
19
20 void check(int &x,int &y,int dx,int dy){
21 int nx=x+dx,ny=y+dy;
22 while( nx>=1&&nx<=h&&ny>=1&&ny<=w&&!vis[nx][ny]){//注意这里是用vis判
23 x=nx;y=ny;
24 nx+=dx;ny+=dy;
25 }
26 }
27
28 void dfs(int step){
29 if( step>l || step>=minn ) return ;
30
31 int hash_now=step;
32 for(int i=1;i<=n;i++){
33 hash_now=hash_now*10+a[i].x;
34 hash_now=hash_now*10+a[i].y;
35 }
36 if( mp[hash_now] ) return ;
37
38 rep(i,1,n){
39 rep(j,0,3){
40 int xx=a[i].x,yy=a[i].y;
41 int lastx=a[i].x,lasty=a[i].y;
42 check(lastx,lasty,dix[j],diy[j]);
43 if( g[lastx][lasty]=='X'&&i==1 ){//注意这里用g判
44 minn=min(minn,step);
45 return ;
46 }
47
48 if( lastx==a[i].x&&lasty==a[i].y ) continue;
49 swap(vis[lastx][lasty],vis[xx][yy]);//注意这里交换vis
50 a[i].x=lastx;
51 a[i].y=lasty;
52 dfs(step+1);
53 swap(vis[lastx][lasty],vis[xx][yy]);
54 a[i].x=xx;
55 a[i].y=yy;
56 }
57 }
58 mp[hash_now]=1;
59 }
60
61 int main()
62 {
63 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
64 minn=100;
65 cin>>n>>w>>h>>l;
66 rep(i,1,h){
67 rep(j,1,w){
68 cin>>g[i][j];
69 if( g[i][j]=='W' ) vis[i][j]=1;
70 else if( g[i][j]>='1'&&g[i][j]<='4'){
71 vis[i][j]=1;
72 a[g[i][j]-'0'].x=i;
73 a[g[i][j]-'0'].y=j;
74 }
75 }
76 }
77 dfs(1);
78 if( minn==100 ) cout<<"NO SOLUTION"<<'\n';
79 else cout<<minn<<'\n';
80 return 0;
81 }