题目链接：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 "); 59 if( !ok ) printf("NO SOLUTION "); 60 else printf("%d ",minn); 61 return 0; 62 }
要想不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"<<' '; 79 else cout<<minn<<' '; 80 return 0; 81 }