?
poj 1324?Holedox Moving
題目地址:?http://poj.org/problem?id=1324
?
題意: 給出一個矩陣中,一條貪吃蛇,占據L長度的格子, 另外有些格子是石頭, 不能通過, 請問蛇到達 (1,1)格子最短距離。?
poj1741、?
明顯的BFS問題, 將每一個可以走的格子進入隊列,
?
格子判斷能否走?(給蛇身體標序號(蛇頭l, 蛇尾1,其他置為0), 當 fabs(cur_num - tmp_num)>=l 的時候,說明蛇的身體已經離開之前的格子了。
?
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;
const int maxn = 50;
const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0}; int n,m,l, mp[maxn][maxn];
bool visited[maxn][maxn];
int queuex[maxn*maxn], queuey[maxn*maxn]; int main(){freopen("in.txt", "r", stdin); int i,j, x, y, k, head, tail, ans, cnt=1; bool flag; int tmp_x, tmp_y, tmp_val, cur_x, cur_y, cur_val; while(scanf("%d %d %d", &n, &m, &l) != EOF){if(n==0 && m==0 && l==0){break; }memset(mp, 0, sizeof(mp)); memset(visited, false, sizeof(visited)); head = tail = 0; for(i=0; i<l; i++){scanf("%d %d", &x, &y); if(i == 0){queuex[head] = x; queuey[head++] = y; }mp[x][y] = l-i; }scanf("%d", &k);for(i=0; i<k; i++){scanf("%d %d", &x, &y); visited[x][y] = true; }ans = -1; flag = false; while(head >= tail){if(flag){ break; }tmp_x = queuex[tail]; tmp_y = queuey[tail++]; tmp_val = mp[tmp_x][tmp_y]; for(i=0; i<4; i++){cur_x = dx[i] + tmp_x; cur_y = dy[i] + tmp_y; if(cur_x == 1 && cur_y == 1){ans = tmp_val + 1; flag = true; break; }if( cur_x >=1 && cur_x <= n && cur_y>=1 && cur_y<=m && \!visited[cur_x][cur_y] && fabs(mp[cur_x][cur_y] - tmp_val)>=l){queuex[head] = cur_x; queuey[head++] = cur_y; mp[cur_x][cur_y] = tmp_val + 1; }}}if(ans != -1){printf("Case %d: %d\n", cnt++, ans-l);}else{printf("Case %d: %d\n", cnt++, ans);}}return 0;
}
poj2352。?