| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
C ++ 果断超时 最朴素的方法G++ 水过#include<stdio.h>
#include<iostream>
#include<queue>
#include<string>
#include<string.h>
using namespace std;
int dx[4] = {1, -1, 0, 0};
int n, m, k;
int dy[4] = {0, 0, 1, -1};
bool mark[22][22][1 << 14];
bool shi[22][22];
struct Node
{
int x, y;
int dir, step;
}st;
int poww(int x, int i)
{
int sum = 1;
for(int j = 0; j < i; j ++)
{
sum *= x;
}
return sum;
}
void bfs(Node st)
{
queue<Node> p;
p.push(st);
mark[st.x][st.y][st.dir] = 1;
Node v, vn;
int dirr[10];
bool yuan[22][22];
while(!p.empty())
{
memset(dirr, 0, sizeof(dirr));
vn = p.front();
p.pop();
if(vn.x == 0 && vn.y == 0)
{
printf("%d\n", vn.step);
return;
}
int count = k - 2, flag = vn.dir;
while(flag)
{
dirr[count--] = flag % 4;
flag /= 4;
}
int xx = vn.x, yy = vn.y, x, y;
memset(yuan, 0, sizeof(yuan));
for(int i = 0; i < k - 1; i++)
{
x = xx - dx[dirr[i]];
y = yy - dy[dirr[i]];
xx = x, yy = y;
yuan[xx][yy] = 1;
}
for(int i = 0; i < 4; i++)
{
int flagg = 0;
v.x = vn.x + dx[i];
v.y = vn.y + dy[i];
v.step = vn.step + 1;
v.dir = 0;
for(int j = 0; j < k - 2; j++)
{
v.dir += poww(4, k - 3 - j) * dirr[j];
}
v.dir += poww(4, k - 2) * i;
if(v.x >= n || v.x < 0 || v.y >= m || v.y < 0) continue;
if(mark[v.x][v.y][v.dir]) continue;
if(yuan[v.x][v.y]) continue;
if(shi[v.x][v.y]) continue;
p.push(v);
mark[v.x][v.y][v.dir] = 1;
}
}
printf("-1\n");
return;
}
int main()
{
int a, b, x, y, p, qq = 1;
while(scanf("%d %d", &n, &m)!=EOF)
{
scanf("%d", &k);
if(n == 0 && m == 0 && k == 0) break;
memset(mark, 0, sizeof(mark));
memset(shi, 0, sizeof(shi));
scanf("%d %d", &a, &b);
a--, b--;
st.x = a, st.y = b;
int step = 0, flag;
for(int i = 0; i < k - 1; i++)
{
scanf("%d %d", &x, &y);
x-- , y--;
if(x < a) flag = 0;
if(x > a) flag = 1;
if(y < b) flag = 2;
if(y > b) flag = 3;
step += poww(4, k - 2 - i) * flag;
a = x, b = y;
}
st.dir = step;
st.step = 0;
scanf("%d", &p);
for(int i = 0; i < p; i++)
{
scanf("%d %d", &x, &y);
x--, y--;
shi[x][y] = 1;
}
printf("Case %d: ", qq++);
bfs(st);
}
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator