tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

AOJ 2620: Trodden Cable

解説スライドの2ページ目の図を見るだけ。*1

#include<stdio.h>
#include<algorithm>
#include<queue>
using namespace std;
const int INF=999999999;
int ver[510][510];
int hor[510][510];
char dir[6]="UDLR";
int dx[]={0,0,-1,1};
int dy[]={-1,1,0,0};
char str[1100];
int dist[510][510];
int visit[510][510];
int main(){
    int W,H,N;
    int fromX,toX,fromY,toY;
    scanf("%d%d%d",&W,&H,&N);
	scanf("%d%d%d%d",&fromX,&fromY,&toX,&toY);
    for(int i=0;i<N;i++){
        int initX,initY;
        scanf("%d%d",&initX,&initY);
        int T;
        scanf("%d%s",&T,str);
        int nowX=initX;
        int nowY=initY;
        for(int j=0;j<T;j++){
            for(int k=0;str[k];k++){
                int toX=nowX;
                int toY=nowY;
                for(int l=0;l<4;l++){
                    if(str[k]==dir[l]){
                        toX+=dx[l];
                        toY+=dy[l];
                    }
                }
                if(toX<0||toX>=W||toY<0||toY>=H)continue;
                if(toX==nowX){
                    ver[nowX][max(nowY,toY)]++;
                }else{
                    hor[max(nowX,toX)][nowY]++;
                }
                nowX=toX;
                nowY=toY;
            }
        }
    }
	/*for(int i=0;i<=H;i++){
		for(int j=0;j<=W;j++)printf("%d ",ver[i][j]);
		printf("\n");
	}*/
    for(int i=0;i<=W;i++)for(int j=0;j<=H;j++)dist[i][j]=INF;
    priority_queue<pair<int,pair<int,int> > >Q;
	dist[fromX][fromY]=0;
	Q.push(make_pair(0,make_pair(fromX,fromY)));
    
    while(Q.size()){
        int cost=-Q.top().first;
        int row=Q.top().second.first;
        int col=Q.top().second.second;
        Q.pop();
        if(visit[row][col])continue;
        visit[row][col]=1;
	//	printf("%d %d: %d\n",row,col,cost);
        for(int i=0;i<4;i++){
            int toX=row+dx[i];
            int toY=col+dy[i];
            int ncost=0;
            if(toX==row)ncost=hor[toX][min(toY,col)];
            else ncost=ver[min(toX,row)][toY];
            if(toX<0||toX>W||toY<0||toY>H||visit[toX][toY]||dist[toX][toY]<=cost+ncost)continue;
            dist[toX][toY]=cost+ncost;
            Q.push(make_pair(-dist[toX][toY],make_pair(toX,toY)));
        }
    }
    int ret=dist[toX][toY];
    
    printf("%d\n",ret);
}

*1:さすがにこの問題文はひどすぎると思う。どっちが人でどっちがケーブルなのかとどっちが辺上を動いてどっちが面上を動くのかが問題文を読んでもまったく分からない。