526互联

cf-1800感想

发布时间 2023-03-26 18:54:21作者: 什么时候才能不困

我是菜鸡！我是菜鸡！我是菜鸡！

虽说挺不想承认的，但是必须得承认了，我是菜鸡，真的，一道题写了两天了，还是wa的结果！恨！！！

看看那道题目·

原题传送门

洛谷镜像

题目描述

You are playing some computer game. One of its levels puts you in a maze consisting of  lines, each of which contains  cells. Each cell either is free or is occupied by an obstacle. The starting cell is in the row  and column  . In one step you can move one square up, left, down or right, if the target cell is not occupied by an obstacle. You can't move beyond the boundaries of the labyrinth.

Unfortunately, your keyboard is about to break, so you can move left no more than  times and move right no more than  times. There are no restrictions on the number of moves up and down since the keys used to move up and down are in perfect condition.

Now you would like to determine for each cell whether there exists a sequence of moves that will put you from the starting cell to this particular one. How many cells of the board have this property?

输入格式

The first line contains two integers  ,  (  ) — the number of rows and the number columns in the labyrinth respectively.

The second line contains two integers  ,  (  ,  ) — index of the row and index of the column that define the starting cell.

The third line contains two integers  ,  (  ) — the maximum allowed number of movements to the left and to the right respectively.

The next  lines describe the labyrinth. Each of them has length of  and consists only of symbols '.' and '*'. The  -th character of the i -th line corresponds to the cell of labyrinth at row  and column  . Symbol '.' denotes the free cell, while symbol '*' denotes the cell with an obstacle.

It is guaranteed, that the starting cell contains no obstacles.

输出格式

Print exactly one integer — the number of cells in the labyrinth, which are reachable from starting cell, including the starting cell itself.

题意翻译

题意描述

你正在玩一款电脑游戏。在其中一关，你位于一个  行  列的迷宫。每个格子要么是可以通过的空地，要么是障碍。迷宫的起点位于第  行第  列。你每一步可以向上、下、左、右中的一个方向移动一格，前提是那一格不是障碍。你无法越出迷宫的边界。

不幸的是，你的键盘快坏了，所以你只能向左移动不超过  格，并且向右移动不超过  格。因为上下键情况良好，所以对向上和向下的移动次数没有限制。

现在你想知道在满足上述条件的情况下，从起点出发，有多少格子可以到达（包括起点）？

输入输出格式

输入格式：

第一行包含两个数  ,表示迷宫的行数和列数。

第二行包含两个数  ,表示起点位于第  行第  列。

第三行包含两个数   ,表示最多向左或向右移动的次数。

接下来  行描述这个迷宫，每行为一个长为  的由 '.' 和 '*' 组成的字符串。 '.' 表示空地， '*' 表示障碍。 输入保证起点不是障碍。

输出格式：

输出一个整数，表示从起点出发可以到达的格子数，包括起点本身。

输入输出样例

输入 #1 
4 5
3 2
1 2
.....
.***.
...**
*....
输出 #1 
10
输入 #2 
4 4
2 2
0 1
....
..*.
....
....
输出 #2 
7

说明/提示

Cells, reachable in the corresponding example, are marked with '+'.

First example:

+++..
+***.
+++**
*+++.

Second example:

.++.
.+*.
.++.
.++.

 题解：

一个迷宫问题，但是限制了左右走的次数。

思路还是挺清晰的。

我写着题的思路大概是先只限制一边，然后遍历结束之后遍历另一边，然后取两个交叉的个数就行啦（看起来好像会超时，但是我是wa了，哈哈哈）

由于本人dfs比bfs熟悉，而且认为能bfs的都可以dfs，所以bfs一直处于不熟悉的状态，一开始也是用dfs写的，发现！！大错特错！dfs和bfs还是有很大区别的，dfs在是深搜，然后在最短路上不好处理，所以发现问题之后我就放弃dfs了，改用dfs。

看一下我dfs的

dfs（错误代码，示范） 
 #include<iostream>
#include<cmath>
using namespace std;
//思路：先只限制一个方向的
const int M = 2020;
char a[M][M];
long long b[M][M];
int m, n;
long long x, y;
int l, r;
int dx[5] = { 0,1,0,-1 };
int dy[5] = { 1,0,-1,0 };//方向数组
int checkl[M][M];
int checkr[M][M];
int stepl[M][M];
int stepr[M][M];
long long ans;
int times = 0;
int ti = 0;
void findl(int x, int y)//没问题
{
	checkl[x][y] = 1;//标记
	b[x][y]++;
	//ans++;
	for (int i = 0; i < 4; i++)
	{
		int x1 = x + dx[i];
		int y1 = y + dy[i];
		if (checkl[x1][y1] == 0 && a[x1][y1] == '.' && times <= l)
		{
			if (i == 2)//左走
			{
				times++;//左走的次数++
			}
			if (stepl[x1][y1] == 0)
			{
				stepl[x1][y1] = times;
			}
			else
			{
				stepl[x1][y1] = min(times, stepl[x1][y1]);
				times = stepl[x1][y1];
			}
			if (times <= l)//无法取到最短的
				findl(x1, y1);
			if (i == 2)
				times--;
		}
	}
	return;
}
void findr(int x, int y)//没问题
{
	checkr[x][y] = 1;//标记
	b[x][y]++;
	if (b[x][y] > 1)
		ans++;
	for (int i = 0; i < 4; i++)
	{
		int x1 = x + dx[i];
		int y1 = y + dy[i];
		if (checkr[x1][y1] == 0 && a[x1][y1] == '.' && ti <= r)
		{
			if (i == 0)//左走
				ti++;//左走的次数++
			if (stepr[x1][y1] == 0)
			{
				stepr[x1][y1] = ti;
			}
			else
			{
				stepr[x1][y1] = min(ti, stepr[x1][y1]);
				ti = stepr[x1][y1];
			}
			if (ti <= r)
				findr(x1, y1);
			if (i == 0)
				ti--;
		}
	}
	return;
}
int main()
{
	cin >> m >> n >> x >> y >> l >> r;
	for (int i = 1; i <= m; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			cin >> a[i][j];
		}
	}
	findl(x, y);
	findr(x, y);
	cout << ans;
	return 0;
}

代码吧

然后改用dfs之后，wa了，暂时还不清楚什么原因。

bfs(22个样例wa了) 
 #include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int M = 2010;
char ma[M][M];
int m, n;
int r, l;
int x, y;
long long ans=1;
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };//方向数组
int check[M][M];
int timesl[M][M];
int timesr[M][M];
int a[M][M];
typedef pair<int, int> pi;
void findl(pi start)
{
	queue<pi>q;//建立队列
	q.push(start);//入队
	memset(check, -1, sizeof check);
	check[start.first][start.second] = 0;
	while (!q.empty())
	{
		pi u = q.front();
		q.pop();
		for (int i = 0; i <4; i++)
		{
			int x1 = u.first + dx[i];
			int y1 = u.second + dy[i];
			if (ma[x1][y1] != '.' || check[x1][y1] == 0)
			{
				continue;
			}
			else 
			{
				check[x1][y1] = 0;//标记
				if (i == 2)//如果向左走
				{
					timesl[x1][y1] = timesl[u.first][u.second] + 1;
				}
				else
				{
					timesl[x1][y1] = timesl[u.first][u.second];
				}
				if (timesl[x1][y1] > l)
					continue;
				a[x1][y1]++;
				//ans++;
				q.push({ x1,y1 });
			}
		}
	}
	return;
}
void findr(pi start)
{
	queue<pi>q;//建立队列
	q.push(start);//入队
	memset(check, -1, sizeof check);
	check[start.first][start.second] = 0;
	while (!q.empty())
	{
		pi u = q.front();
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			int x1 = u.first + dx[i];
			int y1 = u.second + dy[i];
			if (ma[x1][y1] != '.' || check[x1][y1] == 0)
			{
				continue;
			}
			else
			{
				check[x1][y1] = 0;//标记
				if (i == 0)//如果向左走
				{
					timesr[x1][y1] = timesr[u.first][u.second] + 1;
				}
				else
				{
					timesr[x1][y1] = timesr[u.first][u.second];
				}
				if (timesr[x1][y1] > r)
					continue;
				a[x1][y1]++;
				if (a[x1][y1] == 2)
					ans++;
				//ans++;
				q.push({ x1,y1 });
			}
		}
	}
	return;
}
int main()
{
	cin >> m >> n >> x >> y >> l >> r;
	for (int i = 1; i <= m; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			cin >> ma[i][j];
		}
	}
	pi start;
	start.first = x;
	start.second = y;
	findl(start);
	findr(start);
	//for (int i = 1; i <= m; i++)
	//{
	//	for (int j = 1; j <= n; j++)
	//	{
	//		if (a[i][j] == 2)
	//			ans++;
	//	}
	//}
	cout << ans;
	return 0;
}

然后我想着，两次bfs有点耗时，合成一个，然后wa的更多了。

bfs（第10个wa了） 
 #include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int M = 2010;
char ma[M][M];
int m, n;
int r, l;
int x, y;
long long ans=1;
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };//方向数组
int check[M][M];
int checkr[M][M];
int timesl[M][M];
int timesr[M][M];
int a[M][M];
typedef pair<int, int> pi;
void findr(pi start)
{
	queue<pi>q;//建立队列
	q.push(start);//入队
	checkr[start.first][start.second] = 1;
	while (!q.empty())
	{
		pi u = q.front();
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			int x1 = u.first + dx[i];
			int y1 = u.second + dy[i];
			if (ma[x1][y1] != '.' || checkr[x1][y1] == 1)
			{
				continue;
			}
			else
			{
				checkr[x1][y1] = 1;//标记
				if (i == 0)//如果向右走
				{
					timesr[x1][y1] = timesr[u.first][u.second] + 1;
				}
				if (i == 2)//如果向左走
				{
					timesl[x1][y1] = timesl[u.first][u.second] + 1;
				}
				else if (i != 0 && i != 2)
				{
					timesr[x1][y1] = timesr[u.first][u.second];
					timesl[x1][y1] = timesl[u.first][u.second];
				}
				if (timesr[x1][y1] <= r && timesl[x1][y1] <= l)
					ans++;
				else
					continue;
				q.push({ x1,y1 });
			}
		}
	}
	return;
}
int main()
{
	cin >> m >> n >> x >> y >> l >> r;
	for (int i = 1; i <= m; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			cin >> ma[i][j];
		}
	}
	pi start;
	start.first = x;
	start.second = y;
	findr(start);
	cout << ans;
	return 0;
}

暂时只想到这里，debug中，悲伤。