加载中…HDU 3912 Turn Right 2011 模拟 Multi-University Training Contest 8 - Host by HUST
(2011-08-05 09:36:09)
标签：
hdu3912turnright2011模拟it |
分类： 搜索 |
题目描述：
从入口开始，按照右前左后的顺序走，“走出”出口，即最后一步是走出边界的，然后再进入出口，此时，显然面向上方，再按上述方法走回入口，问是否遍历完所有点。
解题报告：
模拟，注意转向的处理，用数组，四个方向+1取模比较方便。
代码如下：
if
(!vst[ii][jj])
{
vst[ii][jj] = 1;
ans++;
}
for(int
i = 0; i < 4; i++)
{
int id = ((tar - 1 + 4) % 4 +
i) % 4;
int tmpa = ii + move[id][0],
tmpb = jj + move[id][1];
if (tmpa >= 0
&& tmpa < n
&& tmpb >= 0
&& tmpb < m
&& g[ii][jj][id] != 1
&& !dp[tmpa][tmpb][id])
{
dp[tmpa][tmpb][id] = true;
return dfs(tmpa, tmpb, id);
}else
{
if (tmpa == tara
&& tmpb == tarb) return true;
}
}
return
false;
int
t;scanf("%d", &t);
while(t--)
{
scanf("%d%d%d%d",
&n, &m, &st,
&ed);
memset(g, 0, sizeof(g));
for(int i = 0; i
< n + n - 1; i++)
{
if (i & 1)
{
for(int j =
0; j < m; j++)
{
int tmp;scanf("%d",
&tmp);
if (tmp)
{
g[i / 2][j][2] = 1;
g[i / 2 + 1][j][0] = 1;
}
}
}else
{
for(int j =
0; j < m - 1; j++)
{
int tmp;scanf("%d",
&tmp);
if (tmp)
{
g[i / 2][j][3] = 1;
g[i / 2][j + 1][1] = 1;
}
}
}
}
memset(vst, 0,
sizeof(vst));
ans = 0;
tara = n, tarb = ed;
memset(dp, 0,
sizeof(dp));
bool flag1 = dfs(0, st,
2);
tara = -1, tarb = st;
memset(dp, 0,
sizeof(dp));
bool flag2 = dfs(n - 1, ed,
0);
while(!flag1 || !flag2) new
int;
if (ans == n * m)
printf("YES\n");
else printf("NO\n");
}
return
0;
从入口开始，按照右前左后的顺序走，“走出”出口，即最后一步是走出边界的，然后再进入出口，此时，显然面向上方，再按上述方法走回入口，问是否遍历完所有点。
解题报告：
模拟，注意转向的处理，用数组，四个方向+1取模比较方便。
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int dp[600][600][4];
int move[4][2] = {-1, 0, 0, -1, 1, 0, 0, 1};
int now;
int g[600][600][4], vst[600][600], st, ed, n, m, ans;
int tara, tarb;
bool dfs(int ii, int jj, int tar)
{
}
int main()
{
}
喜欢
0
赠金笔