代码的逻辑应该是没有问题的,但是就是在dfs函数里面越界的判断出了问题。不管xxx和yyy两个变量的值到底是多少,总是会判断越界。求助
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int m, n, xx, yy, minn = 999999999, c, map[101][101], book[101][101], d[101][101];
int dx[5] = {0, 0, 1, 0, -1};
int dy[5] = {0, 1, 0, -1, 0};
void dfs(int x, int y, int step, int color)
{
if(step > minn)
return;
cout << "x坐标="<< x << ' ' << "y坐标=" << y << endl;
for(int i = 1; i <= 4; i++)
{
int xxx = x + dx[i], yyy = y + dy[i];
cout << "xxx坐标="<< xxx << ' ' << "yyy坐标=" << yyy << endl;
if(xxx >= 1 && xxx <= m && yyy >= 1 && yyy <= m)//出问题的地方
{
if(!book[xxx][yyy])
{
book[xxx][yyy] = 1;
if(xxx == m && yyy == m) //如果到达了终点,更新答案
{
if(step < minn)
minn = step;
}
else//否则没有到达终点
{
if(map[x][y] == map[xxx][yyy]) //当下一格的颜色与当前格子的颜色相同,不需要花费金币
{
cout << "当前颜色:" << map[x][y] << ' ' << "下一颜色:" << map[xxx][yyy] << ' ' << "已用金币:" << step << ' ' << "情况代码:1" << endl;
dfs(xxx, yyy, step, map[xxx][yyy]);
}
if(map[x][y] != map[xxx][yyy] && map[x][y] && map[xxx][yyy]) //如果下一格颜色与当前格子颜色不同且两个格子都不是无色格子,需要使用一枚金币
{
cout << "当前颜色:" << map[x][y] << ' ' << "下一颜色:" << map[xxx][yyy] << ' ' << "已用金币:" << step << ' ' << "情况代码:2" << endl;
dfs(xxx, yyy, step + 1, map[xxx][yyy]);
}
if(map[x][y] != map[xxx][yyy] && map[x][y] && !map[xxx][yyy]) //如果下一格颜色与当前格子颜色不同且下一格是无色格子,需要使用两枚金币来使用魔法
{
cout << "当前颜色:" << map[x][y] << ' ' << "下一颜色:" << map[xxx][yyy] << ' ' << "已用金币:" << step << ' ' << "情况代码:3" << endl;
dfs(xxx, yyy, step + 2, map[x][y]);
}
if(map[x][y] != map[xxx][yyy] && !map[x][y] && map[xxx][yyy]) //如果下一格颜色与当前格子颜色不同且当前格子是无色格子
{
cout << "当前颜色:" << map[x][y] << ' ' << "下一颜色:" << map[xxx][yyy] << ' ' << "已用金币:" << step << ' ' << "情况代码:4" << endl;
if(color == map[xxx][yyy])//如果当前无色格子被魔法变成的颜色等于下一格的颜色
dfs(xxx, yyy, step, map[xxx][yyy]);
else//不等于的话,需要一枚金币
dfs(xxx, yyy, step + 1, map[xxx][yyy]);
}
if(map[x][y] == map[xxx][yyy] && !map[x][y]) //如果当前和下一格都是无色,无法通行
{
cout << "当前颜色:" << map[x][y] << ' ' << "下一颜色:" << map[xxx][yyy] << ' ' << "已用金币:" << step << ' ' << "情况代码:5" << endl;
return;
}
}
book[xxx][yyy] = 0;
}
else
{
cout << "越界了,去世b" << endl;
}
}
else
{
cout << "越界了,去世p" << endl;
}
}
}
int main()
{
int m, n;
cin >> m >> n;
for(int i = 1; i <= n; i++)
{
cin >> xx >> yy >> c;
map[xx][yy] = c + 1;//即0表示无色,1表示红色,2表示黄色
}
for(int i = 1; i <= m; i++)
{
for(int j = 1; j <= m; j++)
cout << map[i][j] << ' ';
cout << endl;
}
cout << endl;
for(int i = 1; i <= m; i++)
{
for(int j = 1; j <= m; j++)
cout << book[i][j] << ' ';
cout << endl;
}
cout << endl;
dfs(1, 1, 0, map[1][1]);
if(minn == 999999999)
cout << -1;
else
cout << minn;
return 0;
}