USACO Section 5.2 Wisconsin Squares - 按要求DFS就行了..

网友投稿 308 2022-08-25

USACO Section 5.2 Wisconsin Squares - 按要求DFS就行了..

这题真搞~就一组数据....囧~~~

按他的要求枚举搜索就ok了..当然要输出字典序最小的解~~~那就按字典序来搜索..除了最开始是确定D..后面的都是先确定较小的A,B,C,D,E..再确定较小的Y..再确定较小的X...如此搜出的第一个解就是字典序最小的答案...

开始还想着Hash...结果写完了样例过了...一交就A了...似乎这题不需要Hash..

Program:

/* ID: zzyzzy12 LANG: C++ TASK: wissqu*/ #include #include #include #include #include #include#include#include #include #define oo 2000000005 #define ll long long #define pi (atan(2)+atan(0.5))*2 using namespace std;char s[6][6];bool used[6][6];int num,have[5];struct node{ char t; int y,x; }way[20];bool ok(int y,int x,char c){ if (used[y][x] || s[y][x]==c) return false; if (s[y][x+1]==c || s[y][x-1]==c || s[y+1][x]==c || s[y-1][x]==c) return false; if (s[y+1][x+1]==c || s[y+1][x-1]==c ) return false; if (s[y-1][x+1]==c || s[y-1][x-1]==c) return false; return true; } void DFS(int step){ int x,y,i; char c; if (step==17) { if (!num) { for (i=1;i<=16;i++) printf("%c %d %d\n",way[i].t,way[i].y,way[i].x); } num++; return; } for (i=0;i<5;i++) if (have[i]) { have[i]--; for (y=1;y<=4;y++) for (x=1;x<=4;x++) if (ok(y,x,'A'+i)) { used[y][x]=true; c=s[y][x]; s[y][x]='A'+i; way[step].t=i+'A'; way[step].y=y; way[step].x=x; DFS(step+1); s[y][x]=c; used[y][x]=false; } have[i]++; } return; }int main() { freopen("wissqu.in","r",stdin); freopen("wissqu.out","w",stdout); int i,j; char c; for (i=0;i<=5;i++) s[0][i]=s[i][0]=s[5][i]=s[i][5]='?'; for (i=1;i<=4;i++) scanf("%s",s[i]+1); num=0; memset(used,false,sizeof(used)); have[0]=have[1]=have[2]=have[4]=3; have[3]=4; for (i=1;i<=4;i++) for (j=1;j<=4;j++) if (ok(i,j,'D')) { c=s[i][j]; s[i][j]='D'; used[i][j]=true; have[3]--; way[1].t='D'; way[1].y=i; way[1].x=j; DFS(2); have[3]++; s[i][j]=c; used[i][j]=false; } printf("%d\n",num); return 0; }

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。

标签：数据
上一篇:椰树为啥戒不掉低俗营销？（椰树广告为什么这么俗）
下一篇:USACO Section 5.3 Window Area - 又一矩形覆盖问题
相关文章

 发表评论

暂时没有评论，来抢沙发吧~