codeforces 510 B. Fox And Two Dots

2015年12月6日 0 作者 CrazyKK

http://codeforces.com/contest/510/problem/B
题意：给定一个maze,用不同的字母代表不同的颜色。问能否找到一个颜色相同的环（失少四个点组成）
思路：dfs一遍，如果遇到之前已经访问过的点，说明成环。需要注意的是，要注意由一个点向某方向移动，然后由反方向移动到该点所造成的误判。所以dfs除了要知道当前的坐标x,y，还要记录之前的坐标px,py.




/* ***********************************************
Author :111qqz
Created Time :2015年12月05日 星期六 21时35分07秒
File Name :code/cf/problem/510B.cpp
************************************************ */

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;



using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=55;
int n,m;
char maze[N][N];
bool vis[N][N];
bool flag;


bool inmaze( int x,int y)
{
    if (x>=0&&x<n&&y>=0&&y<m) return true;
    return false;
}
void dfs( int x,int y,int px,int py)  //要记录当前的x,y是由哪里来的。把因为由px,py到x,y再回到px,py引起的误判剔除。
{					//判cycle方式为：到达一个之前已经到达过的点。
    vis[x][y] = true;
   // cout<<"x:"<<x<<" y:"<<y<<" cur:"<<cur<<endl;
    if (flag) return;
    for ( int i = 0 ; i < 4 ; i++)
    {
	int nx = x + dx4[i] ; 
	int ny = y + dy4[i] ;
	if (nx==px&&ny==py) continue;
	if (inmaze(nx,ny)&&maze[nx][ny]==maze[x][y])
	{
	    if (!vis[nx][ny])
	    {
		dfs(nx,ny,x,y);
	    }
	    else
	    {
		flag = true;
		return ;
	    }
	}
    }
    
}
int main()
{
	#ifndef  ONLINE_JUDGE 
	freopen("code/in.txt","r",stdin);
  #endif

	scanf("%d %d",&n,&m);
	for ( int i = 0 ; i < n ; i++) scanf("%s",maze[i]);
	ms(vis,false);
	flag = false;
	for ( int i = 0 ; i < n ;i++)
	{
	    if (flag) break;
	    for ( int j = 0 ; j < m ; j++)
	    {
		if (flag) break;
		if (!vis[i][j])
		{
		    dfs(i,j,-1,-1);
		}
	    }
	}
	if (flag)
	{
	    puts("Yes");
	}
	else
	{
	    puts("No");
	}

  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

/* ***********************************************

Author :111qqz

Created Time :2015年12月05日星期六 21时35分07秒

File Name :code/cf/problem/510B.cpp

************************************************ */

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <cmath>

#include <cstdlib>

#include <ctime>

#define fst first

#define sec second

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define ms(a,x) memset(a,x,sizeof(a))

typedef long long LL;

using namespace std;

const double eps = 1E-8;

const int dx4[4]={1,0,0,-1};

const int dy4[4]={0,-1,1,0};

const int inf = 0x3f3f3f3f;

const int N=55;

int n,m;

char maze[N][N];

bool vis[N][N];

bool flag;

bool inmaze( int x,int y)

{

if (x>=0&&x<n&&y>=0&&y<m) return true;

return false;

}

void dfs( int x,int y,int px,int py) //要记录当前的x,y是由哪里来的。把因为由px,py到x,y再回到px,py引起的误判剔除。

{ //判cycle方式为：到达一个之前已经到达过的点。

vis[x][y] = true;

// cout<<"x:"<<x<<" y:"<<y<<" cur:"<<cur<<endl;

if (flag) return;

for ( int i = 0 ; i < 4 ; i++)

{

int nx = x + dx4[i] ;

int ny = y + dy4[i] ;

if (nx==px&&ny==py) continue;

if (inmaze(nx,ny)&&maze[nx][ny]==maze[x][y])

{

if (!vis[nx][ny])

{

dfs(nx,ny,x,y);

}

else

{

flag = true;

return ;

}

int main()

{

#ifndef ONLINE_JUDGE

freopen("code/in.txt","r",stdin);

#endif

scanf("%d %d",&n,&m);

for ( int i = 0 ; i < n ; i++) scanf("%s",maze[i]);

ms(vis,false);

flag = false;

for ( int i = 0 ; i < n ;i++)

{

if (flag) break;

for ( int j = 0 ; j < m ; j++)

{

if (flag) break;

if (!vis[i][j])

{

dfs(i,j,-1,-1);

}

if (flag)

{

puts("Yes");

}

else

{

puts("No");

}

#ifndef ONLINE_JUDGE

fclose(stdin);

#endif

return 0;

}

分类目录codeforces

标签dfs

关于作者

CrazyKK

ex-ACMer@hust，stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人！