华师一附中OI组

标题: P2324 [SCOI2005]骑士精神 [打印本页]

---

作者: admin    时间: 2018-5-21 12:17
标题: P2324 [SCOI2005]骑士精神
https://www.luogu.org/problemnew/show/P2324


输入输出格式
输入格式：
第一行有一个正整数T(T<=10)，表示一共有N组数据。接下来有T个5×5的矩阵，0表示白色骑士，1表示黑色骑士，*表示空位。两组数据之间没有空行。

输出格式：
对于每组数据都输出一行。如果能在15步以内（包括15步）到达目标状态，则输出步数，否则输出－1。

输入输出样例
输入样例#1：
2
10110
01*11
10111
01001
00000
01011
110*1
01110
01010
00100
输出样例#1：
7
-1
说明

---

作者: lyc    时间: 2018-5-27 10:47

1. #include<iostream>
   
2. #include<algorithm>
   
3. #include<cstring>
   
4. #include<cstdio>
   
5. const int oo = 0x3f3f3f3f;
   
6. using namespace std;
   
7. int chest[10][10];
   
8. int ans;
   
9. int pd[6][6] = {+0, +0, +0, +0, +0, +0,
   
10.                 +0, +1, +1, +1, +1, +1,
    
11.                 +0, +0, +1, +1, +1, +1,
    
12.                 +0, +0, +0, -1, +1, +1,
    
13.                 +0, +0, +0, +0, +0, +1,
    
14.                 +0, +0, +0, +0, +0, +0
    
15.                };
    
16. int fx[8]={+1,+1,-1,-1,+2,+2,-2,-2};
    
17. int fy[8]={+2,-2,+2,-2,+1,-1,+1,-1};
    
18. bool flag = 0;
    
19. inline int rem(){
    
20.     int ans=0;
    
21.     for(int i=1;i<=5;i++){
    
22.         for(int j=1;j<=5;j++){
    
23.             if(pd[i][j] != chest[i][j]) ans++;
    
24.         }
    
25.     }
    
26.     return ans;
    
27. }
    
28. void dfs(int now, int last, int x, int y)
    
29. {
    
30.     int remain = rem();
    
31.     if(remain + now > 16 || now > ans) return;
    
32.     if(remain == 0)
    
33.     {
    
34.         ans = now;
    
35.         flag = 1;
    
36.         return;
    
37.     }
    
38.     for(int i=0; i<=7; i++)
    
39.     {
    
40.         int nx = x + fx[i];
    
41.         int ny = y + fy[i];
    
42.         if(nx<1 || nx>5 || ny<1 || ny>5 || i == 7-last) continue;
    
43.         swap(chest[nx][ny], chest[x][y]);
    
44.         dfs(now+1, i, nx, ny);
    
45.         swap(chest[nx][ny], chest[x][y]);
    
46.     }
    
47. }
    
48. int t;
    
49. int main()
    
50. {
    
51.     cin>>t;
    
52.     while(t--)
    
53.     {
    
54.         memset(chest, 0, sizeof(chest));
    
55.         flag = 0;
    
56.         ans = oo;
    
57.         int sx,sy;
    
58.         char k;
    
59.         for(int i=1; i<=5; i++)
    
60.             for(int j=1; j<=5; j++)
    
61.             {
    
62.                 cin>>k;
    
63.                 if(k=='*')
    
64.                 {
    
65.                     chest[i][j]=-1;
    
66.                     sx=i;
    
67.                     sy=j;
    
68.                 }
    
69.                 else chest[i][j]= k - '0';
    
70.             }
    
71.         dfs(0, 0, sx, sy);
    
72.         if(!flag)
    
73.         {
    
74.             cout<<-1<<endl;
    
75.             continue;
    
76.         }
    
77.         else cout<<ans<<endl;
    
78.     }
    
79.     return 0;
    
80. }
    

复制代码

luogu最后一个点wa不知道为什么

---

作者: 张笑宇    时间: 2018-6-1 22:54

1. #include<iostream>
   
2. using namespace std;
   
3. int m[6][6]= {0,0,0,0,0,0,
   
4.               0,1,1,1,1,1,
   
5.               0,0,1,1,1,1,
   
6.               0,0,0,-1,1,1,
   
7.               0,0,0,0,0,1,
   
8.               0,0,0,0,0,0,
   
9.              };///0白 1黑 2空格
   
10. int i,j,t,x0,y0,a[6][6],ans;
    
11. int dx[9]={0,-2,-2,-1,-1,1,1,2,2};
    
12. int dy[9]={0,-1,1,-2,2,-2,2,-1,1};
    
13. int done()///完成
    
14. {
    
15.     int id,jd,s=0;
    
16.     for (id=1; id<=5; id++)
    
17.         for (jd=1; jd<=5; jd++)
    
18.         {
    
19.             if (a[id][jd]!=m[id][jd]) s++;
    
20.         }
    
21.     return s;
    
22. }
    
23. void dfs(int x,int y,int sum,int last)///(x,y)空格 sum步数
    
24. {
    
25.     int don=done();
    
26.     if (sum+don>16) return;
    
27.     else if (sum>=ans) return;
    
28.     else if (don==0)
    
29.     {ans=min(ans,sum);return;}
    
30.     else
    
31.         for (int k=1; k<=8; k++)
    
32.         {
    
33.             int tx=x+dx[k];
    
34.             int ty=y+dy[k];
    
35.             if (1<=tx&&tx<=5&&1<=ty&&ty<=5&&(k+last)!=9)///可以搜索
    
36.             {
    
37.                 swap(a[tx][ty],a[x][y]);
    
38.                 dfs(tx,ty,sum+1,k);
    
39.                 swap(a[tx][ty],a[x][y]);
    
40.             }
    
41.         }
    
42. }
    
43. int main()
    
44. {
    
45.     cin>>t;
    
46.     for (int it=1; it<=t; it++)
    
47.     {
    
48.         ans=99999;
    
49.         for (i=1; i<=5; i++)
    
50.         {
    
51.             string s;
    
52.             cin>>s;
    
53.             for (j=1; j<=5; j++)
    
54.             {
    
55.                 if (s[j-1]=='1') a[i][j]=1;
    
56.                 else if (s[j-1]=='0') a[i][j]=0;
    
57.                 else if (s[j-1]=='*')
    
58.                 {
    
59.                     a[i][j]=-1;
    
60.                     x0=i;
    
61.                     y0=j;
    
62.                 }
    
63.             }
    
64.         }
    
65.         dfs(x0,y0,0,0);
    
66.         if (ans<=15) cout<<ans<<endl;
    
67.         else cout<<"-1"<<endl;
    
68.     }
    
69.     return 0;
    
70. }
    

复制代码

---

作者: 张笑宇    时间: 2018-6-1 22:56
判断是否往回走的（k+last）！=9好巧妙
没有想到.......

---

作者: YTC    时间: 2018-7-2 10:01
迭代加深

1. #include<iostream>
   
2. #include<iomanip>
   
3. #include<cstring>
   
4. #include<cstdlib>
   
5. using namespace std;
   
6. const int dx[]={0,-2,-1,1,2,-2,-1,1,2};
   
7. const int dy[]={0,1,2,2,1,-1,-2,-2,-1};
   
8. const int p[6][6]=
   
9. {
   
10.     +0,+0,+0,+0,0,0,
    
11.     +0,+1,+1,+1,1,1,
    
12.     +0,+0,+1,+1,1,1,
    
13.     +0,+0,+0,-1,1,1,
    
14.     +0,+0,+0,+0,0,1,
    
15.     +0,+0,+0,+0,0,0,
    
16. };
    
17. int f[7][7];
    
18. const int base=10;
    
19. int T;
    
20. char c;
    
21. int stx,sty;
    
22. int v[1001];
    
23. int maxd;
    
24. bool ok;
    
25. int ans;
    
26. int rem()
    
27. {
    
28.     int ans=0;
    
29.     for(int i=1;i<=5;i++)
    
30.         for(int j=1;j<=5;j++)
    
31.     {
    
32.         if(f[i][j]!=p[i][j]) ans++;
    
33.     }
    
34.     return ans;
    
35. }
    
36. void dfs(int a,int b,int last,int d)
    
37. {
    
38.      if(d+rem()-1>maxd) return ;//至少走rem（）-1步才能到
    
39. 
    
40.      if(rem()==0)
    
41.      {
    
42.          ok=1;
    
43.          return;
    
44.      }
    
45.      for(int i=1;i<=8;i++)
    
46.      {
    
47.          int x=a+dx[i];
    
48.          int y=b+dy[i];
    
49.          if(x<1||x>5||y<1||y>5||i+last==9) continue;
    
50.          swap(f[a][b],f[x][y]);
    
51.          dfs(x,y,i,d+1);
    
52.          swap(f[a][b],f[x][y]);
    
53.      }
    
54. }
    
55. int main()
    
56. {
    
57.     cin>>T;
    
58.     while(T--)
    
59.     {
    
60.         for(int i=1;i<=5;i++)
    
61.             for(int j=1;j<=5;j++)
    
62.         {
    
63.             cin>>c;
    
64.             if(c=='*')
    
65.             {
    
66.                 f[i][j]=-1;
    
67.                 stx=i;
    
68.                 sty=j;
    
69.             }
    
70.             else f[i][j]=c-'0';
    
71.         }
    
72.     for(maxd=0;maxd<=15;maxd++)
    
73.     {
    
74.         ok=0;
    
75.         dfs(stx,sty,0,0);
    
76.         if(ok) {cout<<maxd<<endl;break;}
    
77.     }
    
78.     if(!ok) cout<<-1<<endl;
    
79.     }
    
80.     return 0;
    
81. }
    

复制代码

---

欢迎光临 华师一附中OI组 (http://hsyit.cn/)

Powered by Discuz! X3.2