Question

C语言编程 求解

你所在的城市爆发了瘟疫，若干个区域已经被感染，你必须尽快逃离这座城市。
你逃离的速度和瘟疫扩散的速度一致，为每小时一个区域（上下左右）。
给出一个n行m列的矩阵，代表城市的n*m个区域，含义如下：
‘.’：居民区，瘟疫可以感染这个区域，你可以在感染前通过。
‘#’：高山，瘟疫不能传播，你也不能通过。
‘J’：你的初始位置，数据保证只有一个。
‘F’：已经被感染的区域，可能有多个。

问你是否可以不被感染而逃离这个城市，如果可以，输出最少需要几个小时，如果不能输出IMPOSSIBLE
Input
第一行一个整数T，表示有T组数据。
每组数据第一行两个整数n和m (1<=n,m<=1,000)，接下来一个n行m列的矩阵代表城市的构造。
Output
对于每组数据，如果能够逃离（走出边界），输出最少需要的小时数，否则输出IMPOSSIBLE。
Sample Input
2
4 4
####
#JF#
#..#
#..#
3 3
###
#J.
#.F
Sample Output
3
IMPOSSIBLE

Answer 1

程序:
#include<stdio.h>
int T,n,m,i,j,k,l,maxn,ans,a0,b0,t;
char c[1002];
int a[1002][1002];
int move[4][2]={{-1,0},{0,-1},{1,0},{0,1}};
int dfs(int x,int y,int t)
{
int ans=maxn,k,l;
for(k=0;k<4;k++)
{
if(a[x+move[k][0]][y+move[k][1]]==-2)
if(ans>t) ans=t;
if(a[x+move[k][0]][y+move[k][1]]>t)
{
l=dfs(x+move[k][0],y+move[k][1],t+1);
if(ans>l) ans=l;
}
}
return ans;
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
{
scanf("%s",c);
for(j=1;j<=m;j++)
{
if(c[j-1]=='#') {a[i][j]=-1;l++;}
else if(c[j-1]=='.') a[i][j]=-8;
else if(c[j-1]=='F') {a[i][j]=0;l++;}
else if(c[j-1]=='J'){a0=i;b0=j;a[i][j]=-8;}
}
}
for(i=0;i<=n+1;i++) a[i][0]=a[i][m+1]=-2;
for(j=0;j<=m+1;j++) a[0][j]=a[n+1][j]=-2;
l=n*m-l;t=-1;
while(l>0)
{
t++;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(a[i][j]==t)
for(k=0;k<4;k++)
if(a[i+move[k][0]][j+move[k][1]]==-8)
{
a[i+move[k][0]][j+move[k][1]]=t+1;
l--;
}
}
maxn=t+5;
ans=dfs(a0,b0,1);
if(ans==maxn) printf("IMPOSSIBLE\n");
else printf("%d\n",ans);
}
return 0;
}
我就没写注释了，大体思想是用数字标记每个地方的状态，然后搜索一下就行。不懂的话可以追问。

Answer 2

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
using namespace std;
inline char getc(void) {
static char buf[1 << 18], *fs, *ft;
return (fs == ft && (ft = (fs = buf) + fread(buf, 1, 1 << 18, stdin)), fs == ft) ? EOF : *fs++;
}
inline int read(void) {
char tmp = getc();
int res = 0;
for(; !isdigit(tmp); tmp = getc());
for(; isdigit(tmp); tmp = getc())
res = ((res + (res << 2)) << 1) + (tmp ^ 0x30);
return res;
}
inline int read(char *s) {
char *p = s;
while(!isgraph(*p = getc()));
while(isgraph(*(++p) = getc()));
*p = '\0';
return p - s;
}
const int MAXN = 1e3 + 10;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
struct DATA{ int x, y; };
void Work(void);
char G[MAXN][MAXN];
int Casenum, N, M, now;
queue<DATA> que1[2], que2[2];
int main() {
Casenum = read();
while(Casenum--) Work();
return 0;
}
void Work(void) {
while(!que1[0].empty()) que1[0].pop();
while(!que1[1].empty()) que1[1].pop();
while(!que2[0].empty()) que2[0].pop();
while(!que2[1].empty()) que2[1].pop();
memset(G, 0x00, sizeof(G));
N = read(), M = read(), now = 0;
for(int i = 1; i <= N; ++i) read(G[i] + 1);
for(int i = 1; i <= N; ++i)
for(int j = 1; j <= M; ++j)
if(G[i][j] == 'J') que1[0].push((DATA){i, j});
else if(G[i][j] == 'F') que2[0].push((DATA){i, j});
while(true) {
DATA u, v;
while(!que2[now&1].empty()) {
u = que2[now&1].front();
que2[now&1].pop();
for(int i = 0; i < 4; ++i) {
v = (DATA){u.x + dx[i], u.y + dy[i]};
if(G[v.x][v.y] != '.') continue;
que2[(now & 1) ^ 1].push(v);
G[v.x][v.y] = 'K';
}
}
while(!que1[now&1].empty()) {
u = que1[now&1].front();
que1[now&1].pop();
for(int i = 0; i < 4; ++i) {
v = (DATA){u.x + dx[i], u.y + dy[i]};
if(!G[v.x][v.y]) {
printf("%d\n", now + 1);
return ;
}
if(G[v.x][v.y] != '.') continue;
que1[(now & 1) ^ 1].push(v);
}
}
if(que1[(now & 1) ^ 1].empty()) {
printf("Impossible!\n"); return ;
}
++now;
}
}

使用C++实现的，来晚了。