NC24821. [USACO 2009 Jan S]Laserphones
描述
The cows have a new laser-based system so they can have casual conversations while out in the pasture which is modeled as a W x H grid of points (1 <= W <= 100; 1 <= H <= 100). The system requires a sort of line-of-sight connectivity in order to sustain communication. The pasture, of course, has rocks and trees that disrupt the communication but the cows have purchased diagonal mirrors ('/' and '\' below) that deflect the laser beam through a 90 degree turn. Below is a map that illustrates the problem. H is 8 and W is 7 for this map. The two communicating cows are notated as 'C's; rocks and other blocking elements are notated as '*'s: 7 . . . . . . . 7 . . . . . . . 6 . . . . . . C 6 . . . . . /-C 5 . . . . . . * 5 . . . . . | * 4 * * * * * . * 4 * * * * * | * 3 . . . . * . . 3 . . . . * | . 2 . . . . * . . 2 . . . . * | . 1 . C . . * . . 1 . C . . * | . 0 . . . . . . . 0 . \-------/ . 0 1 2 3 4 5 6 0 1 2 3 4 5 6 Determine the minimum number of mirrors M that must be installed to maintain laser communication between the two cows, a feat which is always possible in the given test data.输入描述
* Line 1: Two space separated integers: W and H
* Lines 2..H+1: The entire pasture.
输出描述
* Line 1: A single integer: M
示例1
输入:
7 8 ....... ......C ......* *****.* ....*.. ....*.. .C..*.. .......
输出:
3
C++14(g++5.4) 解法, 执行用时: 23ms, 内存消耗: 5480K, 提交时间: 2020-08-21 10:40:11
# include<bits/stdc++.h>
using namespace std;
int tox[5]={0,1,0,-1,0},toy[5]={0,0,1,0,-1};
int n,m,s(9999999),cnt,dp[501][501][5];
char a[501][501];
bool vis[501][501];
void dfs(int x,int y,int direct,int times){
if(direct!=-1 && dp[x][y][direct]<=times) return;
if(direct!=-1) dp[x][y][direct]=times;
if(a[x][y]=='C'){
s=min(s,times);
return;
}
register int i,j,x1,y1;
if(direct!=-1){
x1=x+tox[direct];
y1=y+toy[direct];
if(x1>=1 && x1<=n && y1>=1 && y1<=m && vis[x1][y1]==0 && a[x1][y1]!='*'){
vis[x1][y1]=1;
dfs(x1,y1,direct,times);
vis[x1][y1]=0;
}
}
for(i=1;i<=4;i++){
if(i!=direct){
x1=x+tox[i];
y1=y+toy[i];
if(x1>=1 && x1<=n && y1>=1 && y1<=m && vis[x1][y1]==0 && a[x1][y1]!='*'){
vis[x1][y1]=1;
if(direct!=-1) dfs(x1,y1,i,times+1);
else dfs(x1,y1,i,times);
vis[x1][y1]=0;
}
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int i,j,k;
cin>>m>>n;
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
cin>>a[i][j];
}
}
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
if(a[i][j]=='C'){
memset(dp,999999,sizeof(dp));
vis[i][j]=1;
a[i][j]='*';
dfs(i,j,-1,0);
cout<<s<<endl;
return 0;
}
}
}
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 33ms, 内存消耗: 18772K, 提交时间: 2020-02-26 18:48:15
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
struct zzz
{
int x,y,num,dir;
}q[10000010];
int h=1,t;
int mapp[111][111];
int ex,ey;
int fx[5]={0,1,0,-1,0},
fy[5]={0,0,1,0,-1};
bool flag;
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
{
char c;
cin>>c;
if(c!='*')
{
mapp[i][j]=0x7fffffff;
if(c=='C'&&!flag)
mapp[i][j]=0,q[++t].x=i,q[t].y=j,flag=1;
if(c=='C'&&flag) ex=i,ey=j;
}
else
mapp[i][j]=-1;
}
while(h<=t)
{
for(int i=1;i<=4;i++)
{
int xx=q[h].x+fx[i],yy=q[h].y+fy[i],st=q[h].num;
if(xx<1||yy<1||xx>m||yy>n||mapp[xx][yy]<0) continue;
if(q[h].dir!=i)
if(q[h].dir) st+=1;
if(st<=mapp[xx][yy])
{
mapp[xx][yy]=st;
q[++t].x=xx,q[t].y=yy;
q[t].dir=i;
q[t].num=st;
}
}
h++;
}
if(mapp[ex][ey]<=10000) cout<<mapp[ex][ey];
else cout<<-1;
return 0;
}