C++14(g++5.4) 解法, 执行用时: 2ms, 内存消耗: 484K, 提交时间: 2020-08-20 09:56:46

# include <bits/stdc++.h>
using namespace std;
int n, m, sx, sy, tx, ty;
char maps[1010][1010];
bool book[1010][1010];
int fx[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };
char a[5] = { "dasw" };
int judge(int x, int y)
{
	if (x < 0 || x >= n || y < 0 || y >= m)
		return 0;
	return 1;
}
int flag=0;
void dfs(int x,int y)
{
	if (x == tx && y == ty)
	{
		flag = 1;
		return;
	}
	if(!flag)
	switch (maps[x][y])
	{
	case 'w':
		if (judge(x - 1, y)&&!book[x-1][y])
		{
			book[x - 1][y] = 1;
			dfs(x - 1, y);
		}return;
	case 's':
		if (judge(x + 1, y)&&!book[x+1][y])
		{
			book[x + 1][y] = 1;
			dfs(x + 1, y);
		}return;
	case 'a':
		if (judge(x, y - 1)&&!book[x][y-1])
		{
			book[x][y - 1] = 1;
			dfs(x, y - 1);
		}return;
	case 'd':
		if (judge(x,y+1)&&!book[x][y+1])
		{
			book[x][y + 1] = 1;
			dfs(x,y+1);
		}return;
	case '.':
		int i,nx,ny;
		for (i = 0; i < 4; i++)
		{
			nx = x + fx[i][0];
			ny = y + fx[i][1];
			if (judge(nx, ny) && !book[nx][ny])
			{
				book[nx][ny] = 1;
				maps[x][y] = a[i];
				dfs(nx, ny);
				if (flag)return;
				maps[x][y] = '.';
				book[nx][ny] = 0;
			}
		}
	}
}
int main() {
	scanf("%d %d %d %d %d %d", &n, &m, &sx, &sy, &tx, &ty);
	int i, j;
	for (i = 0; i < n; i++)
		scanf("%s", maps[i]);
	sx--, sy--, tx--, ty--;
	book[sx][sy] = 1;
	dfs(sx, sy);
printf("%d %d %d %d %d %d\n", n,m, sx+1, sy+1, tx+1, ty+1);
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < m; j++)
		{
			if (maps[i][j] == '.')
				printf("w");
			else
				printf("%c", maps[i][j]);
		}
		printf("\n");
	}
}

C++(clang++ 11.0.1) 解法, 执行用时: 3ms, 内存消耗: 640K, 提交时间: 2023-01-02 11:37:57

#include<iostream>
#include<algorithm>
using namespace std;

int n, m,sx, sy, tx, ty;
const int N = 1e3 + 5;
char d[N][N], f[N][N];
bool st[N][N][5];
int dx[4] = { 0,0,-1,1 };
int dy[4] = { 1,-1,0,0 };
char t[4] = { 'd','a','w','s' };

bool dfs(int x, int y) {
	//printf("f[%d][%d]=%c\n", x, y, f[x][y]);
	if (x == tx && y == ty)return 1;
	if (f[x][y] != '.') {
		for (int i = 0; i < 4; i++) {
			if (f[x][y] == t[i]) {
				if (st[x][y][i])return 0;
				st[x][y][i] = 1;
				int a = dx[i] + x, b=dy[i] + y;
				if (a <= 0 || b <= 0 || a > n || b > m)return 0;
				if (dfs(a, b))return 1;
				break;
			}
		}
	}
	else {
		for (int i = 0; i < 4; i++) {
			if (st[x][y][i])continue;
			st[x][y][i] = 1;
		    f[x][y] = t[i];
			int a = x + dx[i], b = y + dy[i];
			if (a <= 0 || b <= 0 || a > n || b > m)continue;
			if (dfs(a, b))return 1;
		}
		f[x][y] = 'a';
	}
	return 0;
}

int main() {
	cin >> n >> m >> sx >> sy >> tx >> ty;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> d[i][j];
			f[i][j] = d[i][j];
		}
	}
	int num=dfs(sx, sy);
    printf("%d %d %d %d %d %d\n",n,m,sx,sy,tx,ty);
	if (num) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				if (f[i][j] != '.')cout << f[i][j];
				else cout << 'a';
			}
			puts("");
		}
	}
	return 0;
}