首页 > 代码库 > UVA 12510/CSU 1119 Collecting Coins DFS
UVA 12510/CSU 1119 Collecting Coins DFS
前年的省赛题,难点在于这个石头的推移不太好处理
后来还是看了阳神当年的省赛总结,发现这个石头这里,因为就四五个子,就暴力dfs处理即可。先把石头当做普通障碍,进行一遍全图的dfs或者bfs,找到可以找的点,然后dfs每次探索新区域的新点即可,想通了这里很好做了
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;char mat[15][15];int vis[15][15];int rock[8][2],cnt;int n,m;int dir[][2]={{1,0},{-1,0},{0,1},{0,-1}};int inq[8];int res,sum;void dfs1(int sx,int sy,int col){ vis[sx][sy]=col; for (int i=0;i<4;i++){ int nx=sx+dir[i][0]; int ny=sy+dir[i][1]; if (nx<0 || nx>=n || ny<0 || ny>=m) continue; if (vis[nx][ny]) continue; if (mat[nx][ny]==‘O‘|| mat[nx][ny]==‘X‘) continue; if(mat[nx][ny]==‘C‘){ res++; } dfs1(nx,ny,col); }}void back(int x,int y,int col){ vis[x][y]=0; for (int i=0;i<4;i++){ int nx=x+dir[i][0]; int ny=y+dir[i][1]; if (nx<0 || ny<0 || nx>=n || ny>=m) continue; if (vis[nx][ny]!=col) continue; back(nx,ny,col); }}int maxn,ans;void proc(int num){ char cc; if (num>=cnt) return; for (int i=0;i<cnt;i++){ if (inq[i]) continue; inq[i]=1; int x=rock[i][0]; int y=rock[i][1]; for (int j=0;j<4;j++){ int dx=x+dir[j][0]; int dy=y+dir[j][1]; if (dx<0 || dx>=n || dy<0 || dy>=m) continue; if (mat[dx][dy]==‘X‘) continue; if (!vis[dx][dy]) continue; int tx=x-dir[j][0]; int ty=y-dir[j][1]; if (tx<0 || tx>=n || ty<0 || ty>=m) continue; if (mat[tx][ty]!=‘.‘ && !vis[tx][ty]) continue; cc=mat[tx][ty]; mat[tx][ty]=‘O‘; mat[x][y]=‘.‘; res=0; dfs1(x,y,i+2); maxn+=res; int tmp=res; ans=max(ans,maxn); proc(num+1); back(x,y,i+2); maxn-=tmp; mat[tx][ty]=cc; mat[x][y]=‘O‘; } proc(num+1); inq[i]=0; }}int main(){ int t,sx,sy; scanf("%d",&t); while (t--) { cnt=0; scanf("%d%d",&n,&m); for (int i=0;i<n;i++){ scanf("%s",mat[i]); for (int j=0;j<m;j++){ vis[i][j]=0; if (mat[i][j]==‘S‘){ sx=i;sy=j;mat[i][j]=‘.‘; } else if (mat[i][j]==‘O‘){ rock[cnt][0]=i; rock[cnt++][1]=j; } } } res=0; dfs1(sx,sy,1); sum=res; maxn=0,ans=0; memset(inq,0,sizeof inq); proc(0); ans+=sum; printf("%d\n",ans); } return 0;}
UVA 12510/CSU 1119 Collecting Coins DFS
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。