苏州网站开发建设电话,深圳宝安区做网站的公司,树莓派搭建wordpress,网站后台模板免费题干#xff1a;
福克斯在玩一款手机解迷游戏#xff0c;这个游戏叫做”两点”。基础级别的时候是在一个nm单元上玩的。像这样#xff1a; 每一个单元有包含一个有色点。我们将用不同的大写字母来表示不同的颜色。
这个游戏的关键是要找出一个包含同一颜色的环。看上图中4…题干
福克斯在玩一款手机解迷游戏这个游戏叫做”两点”。基础级别的时候是在一个n×m单元上玩的。像这样 每一个单元有包含一个有色点。我们将用不同的大写字母来表示不同的颜色。
这个游戏的关键是要找出一个包含同一颜色的环。看上图中4个蓝点形成了一个环。一般的我们将一个序列 d1,d2,...,dk 看成一个环当且仅当它符合下列条件时
1. 这k个点不一样即当 i≠j时 di 和 dj不同。
2. k至少是4。
3. 所有的点是同一种颜色。
4. 对于所有的 1≤i≤k-1: di 和 di1 是相邻的。还有 dk 和 d1 也应该相邻。单元 x 和单元 y 是相邻的当且仅当他们有公共边。
当给出一幅格点时请确定里面是否有环。 Input
单组测试数据。 第一行包含两个整数n和m (2≤n,m≤50):板子的行和列。 接下来n行每行包含一个有m个字母的串表示当前行每一个点的颜色。每一个字母都是大写字母。
Output
如果有环输出Yes否则输出No。
Sample Input
3 4
AAAA
ABCA
AAAA
3 4
AAAA
ABCA
AADA
Sample Output
Yes
No
解题报告 数据水啊纯暴力都能过。 这题其实dfs中的状态加一个前驱的记录就不需要step了这样可以优化时间了。因为我们可以先跑并查集然后一个集合一个集合的搜如果搜到以前搜过的点那就return 1;。 这样好处是不需要一个一个点的搜索了另外这题vis数组是不需要回溯的。 另外算是个dfs换句话来说是搜索的的共同坑点吧那就是对起点的标记因为经常在起点那里就落下一个状态比如【51Nod - 1268】和为K的组合 背包 或 dfs这题。
AC代码
#includebits/stdc.husing namespace std;
int n,m;
int nx[4] {0,1,0,-1};
int ny[4] {1,0,-1,0};
bool vis[55][55];
char maze[55][55];
bool ok(int x,int y) {if(x n x 1 y m y 1) return 1;return 0;
}
bool dfs(int idx,int idy,char tar,int x,int y,int step) {if(x idx y idy step 3 ) {return 1;}for(int k 0; k4; k) {int tx xnx[k];int ty yny[k];if(ok(tx,ty) maze[tx][ty] tar vis[tx][ty] 0) {vis[tx][ty]1;if(dfs(idx,idy,tar,tx,ty,step1)) return 1;}}return 0 ;}
int main()
{while(~scanf(%d%d,n,m)) {int flag 0;memset(vis,0,sizeof vis);for(int i 1; in; i) {scanf(%s,maze[i]1);}for(int i 1; in; i) {for(int j 1; jm; j) {for(int k 0; k4; k) {if(maze[inx[k]][jny[k]] ! maze[i][j]) continue;memset(vis,0,sizeof vis);vis[inx[k]][jny[k]]1;
// vis[i][j]1;if(dfs(i,j,maze[i][j],inx[k],jny[k],0)) {flag1;break;}}if(flag) break;}if(flag) break;}if(flag) puts(Yes);else puts(No);}return 0 ;}
总结 刚开始还是犯了小错误三层for那里最外面两层都写的是n....其实内层应该是m
