CF540C Ice Cave problem solving Report

1 topic link

http://codeforces.com/contest/540/problem/C

2 topic arrangement

2.1 Title: ice cave

2.2 Title Description

You play computer games. Your character stands on one level of a multi-level ice cave. In order to move on, you need to go down one layer. The only way is to fall off the ice.

Your cave level is a rectangular square with n rows and m columns. Each cell consists of either intact ice or broken ice. You can move from each cell to the cell next to your cell (due to some limitations of the game engine, you can't jump in the same place, that is, from a cell to itself). If you move to a broken piece of ice, your character will fall out of it. If you move to a complete piece of ice, the ice on this piece of ice will crack.

Let's number rows from top to bottom with integers from 1 to n, and columns from left to right with integers from 1 to m. Let's express the cell at the intersection of row r and column C as (r, c).

You stay on (r1, c1) this ice, and this ice breaks because you just fell here from a higher level. You need to fall from the cell (r2, c2) because there is an exit to the next floor. Can you do this?

2.3 input format

The first row contains two integers n and m - the number of rows and columns in the cave description.

Each of the next n lines describes the initial state of the cave layer, and each line is composed of m characters "." (i.e. intact ice) and "X" (broken ice).

The next line contains two integers, r1 and c1 -- your initial coordinates. Ensure that the description of the cave contains the character 'X' in the cell (r1,? c1), that is, the ice on the starting cell was initially broken.

The next line contains two integers r2 and c2 -- the coordinates of the cell you need to pass through. The last cell may coincide with the beginning cell.

2.4 output format

If the destination can be reached, print 'YES', otherwise print' NO '.

2.5.1 sample input 1

4 6
X...XX
...XX.
.X..X.
......
1 6
2 2

2.5.2 sample output 1

YES

2.6.1 sample input 2

5 4
.X..
...X
X.X.
....
.XX.
5 3
1 1

2.6.2 sample output 2

NO

2.7.1 sample input 3

4 7
..X.XX.
.XX..X.
X...X..
X......
2 2
1 6

2.7.2 sample output 3

YES

2.8 data scope

about 100 % 100\% 100% data:
1 ≤ n , m ≤ 500 1 \le n,m \le 500 1≤n,m≤500
1 ≤ r 1 ≤ n , 1 ≤ c 1 ≤ m 1 \le r_1 \le n,1 \le c_1 \le m 1≤r1​≤n,1≤c1​≤m
1 ≤ r 2 ≤ n , 1 ≤ c 2 ≤ m 1 \le r_2 \le n,1\le c_2 \le m 1≤r2​≤n,1≤c2​≤m

3 topic meaning analysis

3.1 main idea of the topic

Give you a map. At first, you are on (r1,c1), you can't walk on 'X', and (r2,c2) needs to walk twice, while other grids can only walk once.
Can the above requirements be met and finally stop on (r2,c2)?

3.2 example analysis

As mentioned above.

Solution analysis

This question is actually similar to an ordinary search question, but this question (r2,c2) needs to be walked twice, so we have to deal with this problem. Actually,
The most common way is to search widely for violence, and make a special judgment on (r2,c2). But I have one thing to do:
It is not difficult to find that if you have reached (r2,c2) for the first time, you can succeed as long as there is a grid around you.
Then, don't imitate to protect the surrounding grid first, and then run a wide search again. As long as you can walk (r2,c2), you can
We have reached (r2,c2) for the second time.

4 AC code

ACCode #1

// From realcomplex
// Rating 2401
#include <bits/stdc++.h>

using namespace std;

const int N = 505;
int conf[N][N];

void ini(){
	for(int i = 0;i<N;i++)
		for(int j = 0;j<N;j++)
			conf[i][j] = 3;
}

void dfs(int i,int j){
	conf[i][j]+=1;
	if(conf[i][j]>=3)return;
	dfs(i,j+1);
	dfs(i+1,j);
	dfs(i-1,j);
	dfs(i,j-1);
}

int main(){
	ios_base::sync_with_stdio(false); 
	cin.tie(0);
	cout.tie(0);
	ini();
	int n,m;
	cin >> n >> m;
	char c;
	for(int i = 1;i<=n;i++){
		for(int j = 1;j<=m;j++){
			cin >> c;
			conf[i][j] = (c=='X')+1;
		}
	}
	int c1,c2,e1,e2;
	cin >> c1 >> c2 >> e1 >> e2;
 	conf[c1][c2] = 1;
	dfs(c1,c2);
	if(conf[e1][e2]>=3)
		puts("YES");
	else
		puts("NO"); 
 	return 0;
}

ACCode #002

// From cnnfls_csy
// Rating 2937
#include <iostream>
#include <algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<iomanip>
#include<queue>
#define sqr(x) (x)*(x)
using namespace std;
int dx[5]={0,-1,1,0,0},dy[5]={0,0,0,-1,1};
int n,m,i,j,ex,ey,sx,sy,x,y;
char mp[505][505];
queue<int> qx,qy;
int main()
{
	cin>>n>>m;
	for (i=1;i<=n;i++)
	{
		for (j=1;j<=m;j++)
		{
			cin>>mp[i][j];
		}
	}
	cin>>sx>>sy>>ex>>ey;
	qx.push(sx);
	qy.push(sy);
	while (!qx.empty())
	{
		x=qx.front();
		y=qy.front();
		qx.pop();
		qy.pop();
		for (i=1;i<=4;i++)
		{
			if (mp[x+dx[i]][y+dy[i]]=='.')
			{
				mp[x+dx[i]][y+dy[i]]='X';
				qx.push(x+dx[i]);
				qy.push(y+dy[i]);
			}
			else if (mp[x+dx[i]][y+dy[i]]=='X'&&x+dx[i]==ex&&y+dy[i]==ey)
			{
				cout<<"YES";
				return 0;
			}
		}
	}
	cout<<"NO";
	return 0;
}

ACCode #003

// From Heart_Blue
// Rating 2425
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
#define MAX(a,b) ((a) > (b) ? (a) : (b))
#define MIN(a,b) ((a) < (b) ? (a) : (b))
#define MEM(a,b) memset((a),(b),sizeof(a))
const LL INF = 1e9 + 7;
const int N = 5e2 + 10;
char chess[N][N];
int dx[] = { 0,0,1,-1 };
int dy[] = { -1,1,0,0 };
int flag[N][N];
int main()
{
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	int n, m;
	cin >> n >> m;
	MEM(chess, 'X');
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			cin >> chess[i][j];
		}
	}
	int sx, sy;
	int ex, ey;
	cin >> sx >> sy >> ex >> ey;
	int cnt = 0;
	for (int i = 0; i < 4; i++)
	{
		int x = ex + dx[i];
		int y = ey + dy[i];
		if (chess[x][y] == '.') cnt++;
	}
	if (sx == ex && sy == ey)
	{
		if (cnt > 0) puts("YES");
		else puts("NO");
		return 0;
	}
	if (abs(sx - ex) + abs(sy - ey) == 1)
	{
		if (chess[ex][ey] == 'X')
		{
			puts("YES");
		}
		else
		{
			if (cnt > 0) puts("YES");
			else puts("NO");
		}
		return 0;
	}
	MEM(flag, 0);
	list<pair<int, int>> lp;
	lp.push_back({ sx,sy });
	flag[sx][sy] = 1;
	while (!lp.empty())
	{
		int x, y;
		tie(x, y) = lp.front();
		lp.pop_front();
		for (int i = 0; i < 4; i++)
		{
			int tx = x + dx[i];
			int ty = y + dy[i];
			if (flag[tx][ty]) continue;
			flag[tx][ty] = 1;
			if (chess[tx][ty] == 'X') continue;
			lp.push_back({ tx,ty });
		}
	}
	if (flag[ex][ey])
	{
		if (chess[ex][ey] == 'X') puts("YES");
		else if (cnt > 1) puts("YES");
		else puts("NO");
	}
	else puts("NO");
	return 0;
}