Ricochet Robots

题目链接:https://vjudge.net/problem/Gym-100783E

Ricochet Robots

 

 

 Ricochet Robots

 

 Ricochet Robots

 

 Ricochet Robots

 

 跟上一题有点像:但是还是有所不同,这也是觉得自己傻的地方:上一题只要有一个到目标点就可以,所以可以直接变图(swap),不会改变目标点的位置,因为有一个到目标点就直接标记return了,可是这里要是变图(swap),会把目标点的位置改变,因为这里必须是'1'到目标点,可是如果'2','3',‘4’到目标点的话,会与目标点交换,这时就改变了目标点的位置

WA:

Ricochet Robots
 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 }

 

上一篇:二分搜索 ——(最小值最大化和最大值最小化)


下一篇:【ybt高效进阶1-3-3】最大均值