hdu4740【杭州网赛、模拟、有些搜索？】
hdu4740【杭州网赛、模拟、有点搜索？】
当时看了这题就感觉so easy。。。 本来不想写的，后来感觉是不是可以练一下搜索水平。。
比赛时有人过了就没写。 比赛完了写一下。
实现还不是那么顺利， 囧
本来自己以为这题能练下搜索，其实DFS、BFS都没用到，也许模拟中有点搜索吧。
还是类似方格的东西把外围也设置成未标记要好的多，做题多了也许就有这种感觉了吧。
还有自己忽略了驴 老虎前面是已经走过的路也可以转弯。 BS！！
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#define clr(x) memset(x, 0, sizeof(x))
using namespace std;
const int maxn = 1200;
int dv[maxn][maxn], tv[maxn][maxn];
int n, temp;
//碰到已经走过的点也会转向 不仅是撞墙时。
int main()
{
while(scanf("%d", &n) != EOF)
{
if(!n) break;
memset(dv, -1, sizeof(dv));
memset(tv, -1, sizeof(tv));
int a2, b2, c2, a1, b1, c1, ans;
scanf("%d%d%d",&a1, &b1, &c1);
a1++; b1++;
scanf("%d%d%d",&a2, &b2, &c2);
a2++; b2++;
ans = 0;
for(int i = 1; i <= n; i++) //防止界外。 外围都要包一层
for(int j = 1; j <= n; j++)
{
dv[i][j] = 0;
tv[i][j] = 0;
}
dv[a1][b1] = 1; tv[a2][b2] = 1;
while(true)
{
int ok1 = 0, ok2 = 0, temp;
if(a1 == a2 && b1 == b2) break;
if(c1 == 0) // east
{
temp = b1 + 1;
if(!dv[a1][temp])
{
++b1;
ok1 = 1;
dv[a1][temp] = 1;
}
else if(!dv[a1+1][b1])
{
++a1;
ok1 = 1;
c1 = 1;
dv[a1][b1] = 1;
}
}
else if(c1 == 1) //south
{
temp = a1 + 1;
if(!dv[temp][b1])
{
++a1;
ok1 = 1;
dv[temp][b1] = 1;
}
else if(!dv[a1][b1-1])
{
--b1;
ok1 = 1;
c1 = 2;
dv[a1][b1] = 1;
}
}
else if(c1 == 2) //west
{
temp = b1 - 1;
if(!dv[a1][temp])
{
--b1;
ok1 = 1;
dv[a1][temp] = 1;
}
else if(!dv[a1-1][b1])
{
--a1;
ok1 = 1;
c1 = 3;
dv[a1][b1] = 1;
}
}
else if(c1 == 3) //north
{
temp = a1 - 1;
if(!dv[temp][b1])
{
--a1;
ok1 = 1;
dv[temp][b1] = 1;
}
else if(!dv[a1][b1+1])
{
++b1;
ok1 = 1;
c1 = 0;
dv[a1][b1] = 1;
}
}
if(c2 == 0) // east
{
temp = b2 + 1;
if(!tv[a2][temp])
{
++b2;
ok2 = 1;
tv[a2][temp] = 1;
}
else if(!tv[a2-1][b2])
{
--a2;
ok2 = 1;
c2 = 3;
tv[a2][b2] = 1;
}
}
else if(c2 == 1) //south
{
temp = a2 + 1;
if(!tv[temp][b2])
{
++a2;
ok2 = 1;
tv[temp][b2] = 1;
}
else if(!tv[a2][b2+1])
{
++b2;
ok2 = 1;
c2 = 0;
tv[a2][b2] = 1;
}
}
else if(c2 == 2) //west
{
temp = b2 - 1;
if(!tv[a2][temp])
{
--b2;
ok2 = 1;
tv[a2][temp] = 1;
}
else if(!tv[a2+1][b2])
{
++a2;
ok2 = 1;
c2 = 1;
tv[a2][b2] = 1;
}
}
else if(c2 == 3) //north
{
temp = a2 - 1;
if(!tv[temp][b2])
{
--a2;
ok2 = 1;
tv[temp][b2] = 1;
}
else if(!tv[a2][b2-1])
{
--b2;
ok2 = 1;
c2 = 2;
tv[a2][b2] = 1;
}
}
if(ok1 == 0 && ok2 == 0)
{
ans = -1; break;
}
}
if(ans == -1) printf("-1\n");
else printf("%d %d\n", a1-1, b1-1);
}
return 0;
}
再看看THU的代码。。 有 1 -1 0 0 这种东西。。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
const int MAX_N = 1000 + 10;
int n;
//E,S,W,N
int dx[4] = { 0, 1, 0, -1 }, dy[4] = { 1, 0, -1, 0 };
struct Walker {
int x, y, d, turn;
bool active;
bool vis[MAX_N][MAX_N]; //where had he visited
void read(int turn) {
this->turn = turn;
cin >> x >> y >> d;
active = true;
memset(vis, 0, sizeof vis);
}
bool check(int r, int c) {
return r >= 0 && r < n && c >= 0 && c < n && !vis[r][c];
}
void walk() { //can walk?
//go stright
if (check(x + dx[d], y + dy[d])) {
x += dx[d], y += dy[d];
goto end;
}
d = (d + turn) % 4;
if (check(x + dx[d], y + dy[d])) {
x += dx[d], y += dy[d];
goto end;
}
active = false; //dead >_<
return;
end: {
}
vis[x][y] = true;
}
};
Walker A, B;
int main() {
for (;;) {
cin >> n;
if (n == 0)
break;
A.read(1);
B.read(3);
A.vis[A.x][A.y] = true;
B.vis[B.x][B.y] = true;
for (;;) {
if (!A.active && !B.active)
break; //end!
if (A.x == B.x && A.y == B.y) {
cout << A.x << " " << A.y << endl;
goto end;
}
if (A.active) {
A.walk();
}
if (B.active) {
B.walk();
}
}
cout << -1 << endl;
end: {
}
}
}