修改后34分,2、4、7、9WA,3、6、11、13、15、16TLE,代码如下:
```cpp
#include <iostream>
using namespace std;
struct node{
int sx = 0,sy = 0,ex = 0,ey = 0;
};
int n,m,startx,starty,endx,endy,small = 1e9,book[305][305];
node cs[300];
char a[305][305];
int dx[10] = {1,-1,0,0};
int dy[10] = {0,0,1,-1};
int dfs(int x, int y, int step){
if (x == endx && y == endy){
if (step < small){
small = step;
}
return 0;
}
if (a[x][y] >= 'A' && a[x][y] <= 'Z'){
int sx = cs[int(a[x][y] - 'A')].sx, sy = cs[int(a[x][y] - 'A')].sy, ex = cs[int(a[x][y] - 'A')].ex, ey = cs[int(a[x][y] - 'A')].ey;
if (x == sx && y == sy){
if (book[ex][ey] == 0){
book[ex][ey] = 1;
dfs(ex,ey,step);
book[ex][ey] = 0;
}else{
for (int i = 0; i <= 3; i++){
int new_x = x + dx[i], new_y = y + dy[i];
if (new_x < 1 || new_x > n || new_y < 1 || new_y > m || book[new_x][new_y] > 0 || a[new_x][new_y] == '#'){
continue;
}
book[new_x][new_y]++;
dfs(new_x,new_y,step + 1);
book[new_x][new_y]--;
}
}
}else{
if (book[sx][sy] == 0){
book[sx][sy] = 1;
dfs(sx,sy,step);
book[sx][sy] = 0;
}else{
for (int i = 0; i <= 3; i++){
int new_x = x + dx[i], new_y = y + dy[i];
if (new_x < 1 || new_x > n || new_y < 1 || new_y > m || book[new_x][new_y] > 0 || a[new_x][new_y] == '#'){
continue;
}
book[new_x][new_y]++;
dfs(new_x,new_y,step + 1);
book[new_x][new_y]--;
}
}
}
}else{
for (int i = 0; i <= 3; i++){
int new_x = x + dx[i], new_y = y + dy[i];
if (new_x < 1 || new_x > n || new_y < 1 || new_y > m || book[new_x][new_y] > 0 || a[new_x][new_y] == '#'){
continue;
}
book[new_x][new_y]++;
dfs(new_x,new_y,step + 1);
book[new_x][new_y]--;
}
}
return 0;
}
int main(){
cin >> n >> m;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
cin >> a[i][j];
if (a[i][j] == '@'){
startx = i;
starty = j;
}
if (a[i][j] == '='){
endx = i;
endy = j;
}
if (a[i][j] >= 'A' && a[i][j] <= 'Z'){
if (cs[int(a[i][j] - 'A')].sx == 0){
cs[int(a[i][j] - 'A')].sx = i;
cs[int(a[i][j] - 'A')].sy = j;
}else{
cs[int(a[i][j] - 'A')].ex = i;
cs[int(a[i][j] - 'A')].ey = j;
}
}
}
}
book[startx][starty]++;
dfs(startx,starty,0);
cout << small << endl;
return 0;
}
```
by icypenguin @ 2023-01-19 08:07:41
刚才那次是37分,更改后还是37分.
```cpp
#include <iostream>
using namespace std;
struct node{
int sx = 0,sy = 0,ex = 0,ey = 0;
};
int n,m,startx,starty,endx,endy,small = 1e9,book[305][305];
node cs[300];
char a[305][305];
int dx[10] = {1,-1,0,0};
int dy[10] = {0,0,1,-1};
int dfs(int x, int y, int step, int num){
if (x == endx && y == endy){
if (step < small){
small = step;
}
return 0;
}
if (a[x][y] >= 'A' && a[x][y] <= 'Z'){
int sx = cs[int(a[x][y] - 'A')].sx, sy = cs[int(a[x][y] - 'A')].sy, ex = cs[int(a[x][y] - 'A')].ex, ey = cs[int(a[x][y] - 'A')].ey;
if (x == sx && y == sy){
if (book[ex][ey] == 0){
book[ex][ey] = 1;
dfs(ex,ey,step,1);
book[ex][ey] = 0;
}else{
if (num == 0){
return 0;
}
for (int i = 0; i <= 3; i++){
int new_x = x + dx[i], new_y = y + dy[i];
if (new_x < 1 || new_x > n || new_y < 1 || new_y > m || book[new_x][new_y] > 0 || a[new_x][new_y] == '#'){
continue;
}
book[new_x][new_y]++;
dfs(new_x,new_y,step + 1,0);
book[new_x][new_y]--;
}
}
}else{
if (book[sx][sy] == 0){
book[sx][sy] = 1;
dfs(sx,sy,step,1);
book[sx][sy] = 0;
}else{
if (num == 0){
return 0;
}
for (int i = 0; i <= 3; i++){
int new_x = x + dx[i], new_y = y + dy[i];
if (new_x < 1 || new_x > n || new_y < 1 || new_y > m || book[new_x][new_y] > 0 || a[new_x][new_y] == '#'){
continue;
}
book[new_x][new_y]++;
dfs(new_x,new_y,step + 1,0);
book[new_x][new_y]--;
}
}
}
}else{
for (int i = 0; i <= 3; i++){
int new_x = x + dx[i], new_y = y + dy[i];
if (new_x < 1 || new_x > n || new_y < 1 || new_y > m || book[new_x][new_y] > 0 || a[new_x][new_y] == '#'){
continue;
}
book[new_x][new_y]++;
dfs(new_x,new_y,step + 1,0);
book[new_x][new_y]--;
}
}
return 0;
}
int main(){
cin >> n >> m;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
cin >> a[i][j];
if (a[i][j] == '@'){
startx = i;
starty = j;
}
if (a[i][j] == '='){
endx = i;
endy = j;
}
if (a[i][j] >= 'A' && a[i][j] <= 'Z'){
if (cs[int(a[i][j] - 'A')].sx == 0){
cs[int(a[i][j] - 'A')].sx = i;
cs[int(a[i][j] - 'A')].sy = j;
}else{
cs[int(a[i][j] - 'A')].ex = i;
cs[int(a[i][j] - 'A')].ey = j;
}
}
}
}
book[startx][starty]++;
dfs(startx,starty,0,0);
cout << small << endl;
return 0;
}
```
by icypenguin @ 2023-01-19 09:35:23