CodeForces/510B

摘要

题目链接	难度等级	完成状态	完成分数	最后编辑时间	失误原因（初次提交分数）
Fox And Two Dots	★☆☆☆☆	答案正确	100	2015-02-25 17:40:14	mn打反（23）

• 来自寒假练习：2015 Winter Day 2 div2 G题
• 原题链接：http://codeforces.com/problemset/problem/510/B

题意

找出n*m地图上能形成至少四个点不重回路的路线。

题解

dfs，找一个数组记录每个点的深度以保证至少四个点不重。

代码

510B.cpp代码已折叠 展开折叠内容

显示/移除行号 #include<cstdio> #include<iostream> #include<string> #include<vector> #include<iomanip> #include<algorithm> #include<cstring> #include<cmath> #include<bitset> #include<set> #include<sstream> using namespace std; #define llu unsigned long long #define lld long long #define ci const lld& #define si(n) scanf("%lld",&n) #define f0(i,n) for(lld i=0;i!=n;++i) int track[60][60]={},sx[4]={1,0,-1,0},sy[4]={0,1,0,-1}; lld n,m; string s[60]={}; void dfs(ci x,ci y,ci deep,const char& c) { if(x<0||y<0||x>=n||y>=m)return; if(s[x][y]!=c)return; //cout<<x<<" "<<y<<" "<<deep<<endl; if(track[x][y]&&deep-track[x][y]>=4) { cout<<"Yes"; exit(0); } if(track[x][y])return; track[x][y]=deep; f0(i,4) dfs(x+sx[i],y+sy[i],deep+1,c); } int main() { si(n);si(m); f0(i,n)cin>>s[i]; f0(i,n)f0(j,m)//fixed:n->m// { memset(track,0,sizeof(track)); dfs(i,j,1,s[i][j]); } cout<<"No"; exit(0); }