如果要指导我的话就在这个帖子吧
那个帖子沉了，不好翻
by ZhangJiahao0918 @ 2020-03-20 21:54:06
求改码风qwq
by JohnJoeZhu @ 2020-03-20 21:54:55
@[JohnJoeZhu](/user/144523)
等我去我们学校的OJ格式化一下？
by ZhangJiahao0918 @ 2020-03-20 21:56:09
码风清奇。。。。
by 打表大蒟蒻 @ 2020-03-20 21:56:09
@[JohnJoeZhu](/user/144523)
好了
```cpp
#include <bits/stdc++.h>
using namespace std;
int n = 0;
int k = 0;
int w = 0;
int v = 0;
int x = 0;
int y = 0;
int ans = 0;
int check = 0;
int colour = 0;
int p[1111][1111];
int t[1111][1111];
bool l[1111][1111];
struct CHESS {
int x = 0;
int y = 0;
int ans = 0;
int colour = 0;
bool check = true;
};
CHESS s[1111111];
void CHECK(int x, int y) {
check = 0;
if (p[x][y] == 2) {
if (colour == 2) {
w++;
check = 1;
s[w].x = x;
s[w].y = y;
s[w].ans = ans;
s[w].colour = 2;
s[w].check = false;
} else {
w++;
check = 1;
s[w].x = x;
s[w].y = y;
s[w].ans = ans + 1;
s[w].colour = 2;
s[w].check = false;
}
}
if (p[x][y] == 1) {
if (colour == 2) {
w++;
check = 1;
s[w].x = x;
s[w].y = y;
s[w].ans = ans + 1;
s[w].colour = 1;
s[w].check = false;
} else {
w++;
check = 1;
s[w].x = x;
s[w].y = y;
s[w].ans = ans;
s[w].colour = 1;
s[w].check = false;
}
}
if (p[x][y] == 0) {
if (s[v].check == false) {
w++;
check = 1;
s[w].x = x;
s[w].y = y;
s[w].ans = ans + 2;
s[w].colour = colour;
s[w].check = true;
}
}
return;
}
void BFS(int x, int y, int z, int c) {
w++;
check = 1;
s[w].x = x;
s[w].y = y;
s[w].ans = z;
s[w].colour = c;
s[w].check = false;
t[1][1] = 0;
l[1][1] = true;
while (v < w) {
v++;
x = s[v].x;
y = s[v].y;
ans = s[v].ans;
colour = s[v].colour;
if (x - 1 >= 1) {
CHECK(x - 1, y);
if (l[x - 1][y] == false && check) {
l[x - 1][y] = true;
t[x - 1][y] = s[w].ans;
} else if (l[x - 1][y] != false && check) {
if (s[w].ans < t[x - 1][y]) {
t[x - 1][y] = s[w].ans;
} else {
w--;
}
}
}
if (y - 1 >= 1) {
CHECK(x, y - 1);
if (l[x][y - 1] == false && check) {
l[x][y - 1] = true;
t[x][y - 1] = s[w].ans;
} else if (l[x][y - 1] != false && check) {
if (s[w].ans < t[x][y - 1]) {
t[x][y - 1] = s[w].ans;
} else {
w--;
}
}
}
if (x + 1 <= k) {
CHECK(x + 1, y);
if (l[x + 1][y] == false && check) {
l[x + 1][y] = true;
t[x + 1][y] = s[w].ans;
} else if (l[x + 1][y] != false && check) {
if (s[w].ans < t[x + 1][y]) {
t[x + 1][y] = s[w].ans;
} else {
w--;
}
}
}
if (y + 1 <= k) {
CHECK(x, y + 1);
if (l[x][y + 1] == false && check) {
l[x][y + 1] = true;
t[x][y + 1] = s[w].ans;
} else if (l[x][y + 1] != false && check) {
if (s[w].ans < t[x][y + 1]) {
t[x][y + 1] = s[w].ans;
} else {
w--;
}
}
}
}
}
int main() {
int x;
int y;
int z;
cin >> k;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> x;
cin >> y;
cin >> z;
p[x][y] = z + 1;
}
BFS(1, 1, 0, p[1][1]);
if (l[k][k]) {
cout << t[k][n] << endl;
} else {
cout << -1 << endl;
}
return 0;
}
```
我尽力了
by ZhangJiahao0918 @ 2020-03-20 21:57:24
不过话说这题能用dfs+剪枝过
by 打表大蒟蒻 @ 2020-03-20 21:57:46
不改码风很难查啊qwq@[ZhangJiahao0918](/user/279222)
by JohnJoeZhu @ 2020-03-20 21:57:58
@[打表大蒟蒻](/user/181750)
我们教练让我们用BFS
我也没办法啊
by ZhangJiahao0918 @ 2020-03-20 21:58:07
@[JohnJoeZhu](/user/144523)
我再改改？
by ZhangJiahao0918 @ 2020-03-20 21:58:21
能不能去掉换行qwq
by JohnJoeZhu @ 2020-03-20 21:58:43