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