【Codeforces Round #301 (Div. 2) C】 Ice Cave

给你一个n*m的地图。每个地图为0的时候可以安全走过,且走过后变成1. (一定要离开之后才会变成1) 而为1的则走过之后会掉入下一层。你一开始在初始位置(x1,y1); 且你想到达位置(x2,y2); 且要求到达(x2,y2)并且掉进下一层。保证(x1,y1)的状态为1. 问你可行与否

【题解】
首先如果x1,y1和x2,y2重合。
那么判断一下周围有没有可以走的0状态就好->走过去再走回来
如果没有就无解

如果不重合。
那么首先判断一下(x1,y1)能否到达(x2,y2);
如果不可以则无解。
如果可以
如果x2,y2状态为1,则有解
否则
看一下(x2,y2)周围是否有两个以上的状态为0的点。(要走到(x2,y2)然后出去再回来)
或者只有一个状态为0的点,且(x2,y2)和(x1,y1)相邻则有解。
否则无解。

【代码】

#include <bits/stdc++.h>
using namespace std;

const int N = 500;
const int dx[4] = {0,0,1,-1};
const int dy[4] = {1,-1,0,0};

int n,m,r1,c1,r2,c2;
char s[N+10][N+10];
bool can[N+10][N+10];
bool bo[N+10][N+10];

int cnt(int x,int y){
	int num = 0;
 	for (int i = 0;i < 4;i++){
 		int tx = x + dx[i],ty = y + dy[i];
 		if (tx<1 || tx > n) continue;
 		if (ty<1 || ty > m) continue;
 		num += can[tx][ty];
 	}
 	return num;
}

void youjie(){
	puts("YES");
	exit(0);
}

void wujie(){
	puts("NO");
	exit(0);
}

bool dfs(int x,int y){
	if (x==r2 && y == c2) return true;
	if (bo[x][y] || (!can[x][y] && !(x==r1 && y==c1))) return false;
	bo[x][y] = true;	
	bool f = false;
	for (int i = 0;i < 4;i++){
		int tx = x + dx[i],ty = y + dy[i];
		f = f|dfs(tx,ty);
	}
	return f;
}

int main(){
	#ifdef LOCAL_DEFINE
	    freopen("rush_in.txt", "rt", stdin);
	#endif
	scanf("%d%d",&n,&m);
	for (int i = 1;i <= n;i++) scanf("%s",s[i]+1);
	for (int i = 1;i <= n;i++)
		for (int j = 1;j <= m;j++)
			if (s[i][j]=='X')
				can[i][j] = 0;
			else
				can[i][j] = 1;
	scanf("%d%d",&r1,&c1);
	scanf("%d%d",&r2,&c2);
	if (r1 == r2 && c1 == c2){
		if (cnt(r1,c1)>0) youjie();
		wujie();
	}
	if (!dfs(r1,c1))
		wujie();	
	else{
		if (!can[r2][c2]) youjie();
		int cur = cnt(r2,c2);
		if (cur > 1) youjie();
		if (cur == 1 && (abs(r1-r2)+abs(c1-c2))==1) youjie();
		wujie();
	}
	return 0;
}

【Codeforces Round #301 (Div. 2) C】 Ice Cave

相关推荐