首页 > 代码库 > HDU 4478 Where is King

HDU 4478 Where is King

2024-07-27 22:52:45   220人阅读

题目大意：

一个王可以向周围8个方格走，如果都不通留在原地，t秒后，他可能存在的位置数

 

这题数据量过大，我们需要通过奇偶性判断，如果t = 0可以到达，说明 t=2,4,6.。。。都可以到达

所以我这用dp[N][N][2] 来记录x，y位置上奇数和偶数时间分别到达那点的最短时间，如果不存在，用-1表示

 

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <queue> 5 using namespace std; 6 const int N = 105; 7 int dp[N][N][2],n,t,x,y,vis[N][N]; 8 char mat[N][N]; 9 int dir[8][2] = {{1,0},{-1,0},{0,1},{0,-1},{1,-1},{1,1},{-1,1},{-1,-1}};10 11 struct Node{12     int x,y;13     Node(int x,int y):x(x),y(y){}14 };15 16 queue<Node> q;17 18 void bfs()19 {20     q.push(Node(x,y));21     vis[x][y] = 1;22     while(!q.empty()){23         Node t = q.front();24         q.pop();25         vis[t.x][t.y]=0;26 27         for(int i=0;i<8;i++){28             int xx = t.x + dir[i][0];29             int yy = t.y + dir[i][1];30             if(xx>=1&&xx<=n&&yy>=1&&yy<=n&&mat[xx][yy] == ‘.‘){31                 int flag = 0;32                 if((dp[xx][yy][0] < 0 || dp[xx][yy][0] > dp[t.x][t.y][1] + 1) && dp[t.x][t.y][1] >= 0)33                 {34                     dp[xx][yy][0] = dp[t.x][t.y][1] + 1;35                     flag = 1;36                 }37                 if((dp[xx][yy][1] < 0 || dp[xx][yy][1] > dp[t.x][t.y][0] + 1) && dp[t.x][t.y][0] >= 0)38                 {39                     dp[xx][yy][1] = dp[t.x][t.y][0] + 1;40                     flag = 1;41                 }42 43                 if(flag && !vis[xx][yy])44                 {45                     vis[xx][yy]=1;46                     q.push(Node(xx,yy));47                 }48             }49         }50     }51 }52 int main()53 {54     //freopen("test.in","rb",stdin);55     //cout << "Hello world!" << endl;56     int C;57     scanf("%d",&C);58     while(C--){59         scanf("%d%d%d%d",&n,&t,&x,&y);60         for(int i=1;i<=n;i++)61             scanf("%s",mat[i]+1);62 63         memset(vis,0,sizeof(vis));64         memset(dp,-1,sizeof(dp));65         dp[x][y][0]=0;66 67         bfs();68 69         int tmp = t&1;70         int ans = 0;71         for(int i=1;i<=n;i++){72             for(int j=1;j<=n;j++){73                 if(dp[i][j][tmp]!=-1 && dp[i][j][tmp]<=t)74                     ans++;75             }76         }77         printf("%d\n",max(ans,1));78     }79     return 0;80 }

 

HDU 4478 Where is King


联系
我们