首页 > 代码库 > 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