上学 Compile Error 0 分

叶安槿 · 2025 年7 月 25 日 03:02

2.  上学
题目ID：6015必做题100分
最新提交：
Compile Error
0 分
历史最高：
Wrong Answer
20 分
时间限制: 1000ms
空间限制: 524288kB
题目描述
鱼大大就读的学校每天都有检查出勤的楷(e)模(xin)学委。刚巧这天鱼大大起床迟了一些，为了不被这些楷(e)模(xin)学委记录扣分，鱼大大需要挑一条距离最短的小路上学。

身为鱼大大的好朋友，你深知鱼大大的苦楚：鱼大大这个小短腿，每次迈步都只能往上下左右走一格，而学校又在距离鱼大大家直线距离最远的地方，要是不好好规划肯定会迟到。于是你便自告奋勇在鱼大大起床刷牙吃早饭的时候，在地图上帮鱼大大选出一条最快到达学校的路程，并告诉鱼大大这条路的距离以及路线。

----------------------------------------------------

注：
鱼大大的家在地图左上角(1,1)，起点不算入路径长度
学校在地图右下角 (n,m) 。

地图上的#为坑，鱼大大遇到会掉进去，也跨不过去，不能走。

地图大小为N*M。

输入格式
第一行两个整数 N， M(1 < N,M ≤ 1000)

接下来N行，每行M个字符，表示鱼大大能否通过相应位置的区域。字符只可能是 . 或 #。

. 表示鱼大大可以走的路。

#表示鱼大大不能跨过的坑。

输出格式
如果无法到达学校，输出 -1

否则

第一行一个整数表示路径长度

接下来若干行，每行包含两个用空格隔开的整数，表示鱼大大依次通过的区域的坐标。

（若是有多条最短路径，输出其中任何一条即可）

样例
Input 1
5 8
..#...##
#.#.#.##
#...#...
#.#.#.#.
....#.#.
Output 1
15
1 1
1 2
2 2
3 2
3 3
3 4
2 4
1 4
1 5
1 6
2 6
3 6
3 7
3 8
4 8
5 8
样例解释
鱼大大依次通过的区域的坐标。

数据范围
1 < N, M ≤ 1000

/*
2.  上学

记录路径
记录每个点找到最短路时的
上一个点的坐标 

queue<int> q;

struct node {
	int x, y;
} pre[N][N];

while (!q.empty()){
	q.front();
	q.pop();
	
	int x, y;
	
	for (){
		int nx, ny;
		if (越界) continue;
		
		vis[nx][ny = true;
		pre[nx][ny] = {now.x, now.y};
		q.push();
	}
}

找路径代码：
从终点出发
int x = n, y = m;

while (x == 0 && y == 0) {
	cout << x << " " << y << "\n";
	
	if (x == 1 && y == 1) break;
	node t = pre[x][y];
	x = t.x;
	y = t.y;
}

题目需要从起点输出到重点，注意需要存下来倒序输出 
*/

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;

int n, m;

int dx[] = {0, 1, 0, -1};
int dy[] = {-1, 0, 1, 0};
bool vis[N][N];
char s[N][N];

int cnt = 0;

struct node {
	int x, y;
	int d;
} pre[N][N];

queue<node> q;

bool bfs(int x, int y) {
	q.push(node{x, y, 0});
    vis[x][y] = true;
    
//	if (x == n && y == m) {
	//	cnt++;
	//	return 0;
//	}
	
	while (!q.empty()) {
		node now = q.front();
		q.pop();
	
		//int x, y;
	
		for (int i = 0; i < 4; i++) {
			int nx = now.x + dx[i], ny = now.y + dy[i];
			if (nx < 0 || nx > n || ny < 0 || ny > m || vis[nx][ny] || s[nx][ny] == '#') continue;
			
			vis[nx][ny] = true;
			pre[nx][ny] = {now.x, now.y};
			q.push(node{nx, ny, now.d + 1});
		}
		
		int xx = n, yy = m;
	
		if (xx == 0 && yy == 0) {
			cout << now.d + 1;
			return 1;
		}
		
		if (!vis[xx][yy]) {
			cout << -1;
			return 0;
		}
		
		while (1) {
			cout << xx << " " << yy << "\n";
		
			node t = pre[xx][yy];
			xx = t.x;
			yy = t.y;
		}	
	}
	
	
}

int main ()
{
	cin >> n >> m;
	
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> s[i][j];
			s[i][j] = s[i][j] + '#';

            bfs(i, j);
		}
	}
	
	return 0;
}

周思林 · 2025 年7 月 25 日 03:09

（帖子已被作者删除）

周思林 · 2025 年7 月 25 日 03:21

老师不是讲过了吗

韦新宇 · 2025 年7 月 25 日 03:29

const int N = 1e6 + 10;

(1 < N,M ≤ 1000)

？？？数组开1e6?
1e3就够了吧

叶安槿 · 2025 年7 月 25 日 03:58

/*
2.  上学

记录路径
记录每个点找到最短路时的
上一个点的坐标 

queue<int> q;

struct node {
	int x, y;
} pre[N][N];

while (!q.empty()){
	q.front();
	q.pop();
	
	int x, y;
	
	for (){
		int nx, ny;
		if (越界) continue;
		
		vis[nx][ny = true;
		pre[nx][ny] = {now.x, now.y};
		q.push();
	}
}

找路径代码：
从终点出发
int x = n, y = m;

while (x == 0 && y == 0) {
	cout << x << " " << y << "\n";
	
	if (x == 1 && y == 1) break;
	node t = pre[x][y];
	x = t.x;
	y = t.y;
}

题目需要从起点输出到重点，注意需要存下来倒序输出 
*/

#include <bits/stdc++.h>

using namespace std;

const int N = 1e3 + 10;

int n, m;

int dx[] = {0, 1, 0, -1};
int dy[] = {-1, 0, 1, 0};
bool vis[N][N];
char s[N][N];

int cnt = 0;

struct node {
	int x, y;
	int d;
} pre[N][N];

queue<node> q;

bool bfs(int x, int y) {
	q.push(node{x, y, 0});
    vis[x][y] = true;
    
//	if (x == n && y == m) {
	//	cnt++;
	//	return 0;
//	}
	
	while (!q.empty()) {
		node now = q.front();
		q.pop();
	
		//int x, y;
	
		for (int i = 0; i < 4; i++) {
			int nx = now.x + dx[i], ny = now.y + dy[i];
			if (nx < 0 || nx > n || ny < 0 || ny > m || vis[nx][ny] || s[nx][ny] == '#') continue;
			
			vis[nx][ny] = true;
			pre[nx][ny] = {now.x, now.y};
			q.push(node{nx, ny, now.d + 1});
		}
		
		int xx = n, yy = m;
	
		if (xx == 0 && yy == 0) {
			cout << now.d + 1;
			return 1;
		}
		
		if (!vis[xx][yy]) {
			cout << -1;
			return 0;
		}
		
		while (1) {
			cout << xx << " " << yy << "\n";
		
			node t = pre[xx][yy];
			xx = t.x;
			yy = t.y;
		}	
	}
	
	
}

int main ()
{
	cin >> n >> m;
	
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> s[i][j];
			s[i][j] = s[i][j] + '#';

            bfs(i, j);
		}
	}
	
	return 0;
}

TLE 0

姜梓堉 · 2025 年7 月 25 日 04:08

s[i][j] = s[i][j] + '#';

这句干嘛的
输出方案也不对，不可能是在bfs里面的，还有边界也不对

叶安槿 · 2025 年7 月 25 日 04:51

说实话，不知道，边界……不知道

叶安槿 · 2025 年7 月 25 日 04:54

1965593
C++14	
Memory Limit Exceeded
0 分		2025-07-25 12:53:59UTC+8
1965588
C++14	
Time Limit Exceeded
0 分		2025-07-25 12:52:54UTC+8
1965117
C++14	
Time Limit Exceeded
0 分		2025-07-25 11:55:37UTC+8
1965110
C++14	
Memory Limit Exceeded
0 分		2025-07-25 11:55:14UTC+8
1962847
C++14	
Compile Error
0 分		2025-07-25 10:31:39UTC+8
1962419
C++14	
Memory Limit Exceeded
0 分		2025-07-25 10:16:06UTC+8
1961917
C++14	
Time Limit Exceeded
0 分		2025-07-25 09:57:22UTC+8
1961634
C++14	
Wrong Answer
20 分		2025-07-25 09:45:51UTC+8
1961572
C++14	
Time Limit Exceeded
10 分		2025-07-25 09:43:06UTC+8
1961565
C++14	
Runtime Error
10 分		2025-07-25 09:42:41UTC+8
1961558
C++14	
Compile Error
0 分		2025-07-25 09:42:34UTC+8
1961541
C++14	
Runtime Error
10 分		2025-07-25 09:42:21UTC+8

五颜六色各种各样的错误

姜梓堉 · 2025 年7 月 25 日 08:20

…不知道就删掉，边界是1-n合法，你写的0-n合法

陈羽墨 · 2025 年7 月 25 日 08:23

666,竟然是姜老师

胡浩东 · 2025 年7 月 25 日 09:18

你猜while(1)会不会死循环

姜梓堉 · 2025 年7 月 25 日 10:59

（帖子已被作者删除）

叶安槿 · 2025 年7 月 25 日 12:36

Memory Limit Exceeded 0 分

你猜

叶安槿 · 2025 年7 月 25 日 13:05

已 Accepted 100 分

可关帖，此贴结