Submission #61181

---

Source Code Expand

#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <vector>

using namespace std;

#define reps(i,f,n) for(int i=f; i<int(n); ++i)
#define rep(i,n) reps(i,0,n)
#define debug(x) cerr<<#x<<" = "<<(x)<<endl;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;

const int INF = 1001001001;

struct Data
{
	int y, x, dir, next, cost;
	Data(int y, int x, int dir, int next, int cost) : y(y),x(x),dir(dir),next(next),cost(cost){}
	bool operator< (const Data& d)const {
		return cost > d.cost;
	}
};

bool visited[101][101][110][4];
pii memo[100][100][26][4];
int main()
{
	int h, w, l;
	scanf("%d%d%d", &h, &w, &l);
	
	char str[128];
	scanf("%s", str);
	
	char board[128][128];
	rep(i, h)
		scanf("%s", board[i]);
	
	rep(i, 100) rep(j, 100) rep(k, 26) rep(l, 4)
		memo[i][j][k][l].first = -1;

	rep(i, h) rep(j, w){
		rep(k, 4){
			const int dy[] = {-1, 0, 0, 1};
			const int dx[] = {0, 1, -1, 0};
			int py = i, px = j;
			for(;;){
				py += dy[k];
				px += dx[k];
				if(py<0 || h<=py || px<0 || w<=px)
					break;
				
				int c = board[py][px] - 'a';
				if(memo[i][j][c][k].first == -1){
					memo[i][j][c][k] = pii(py, px);
				}
			}
		}
	}
	
	priority_queue<Data> Q;
	rep(i, h) rep(j, w){
		Q.push(Data(i, j, -1, 0, 0));
	}

	int ans = INF;
	while(!Q.empty()){
		Data d = Q.top();
		Q.pop();
		if(visited[d.y][d.x][d.next][d.dir])
			continue;
		visited[d.y][d.x][d.next][d.dir] = true;
		
		rep(i, 4){
			if(d.dir == i) continue;
			pii next = memo[d.y][d.x][str[d.next]-'a'][i];
			if(next.first == -1)
				continue;
			int nextcost = d.cost + abs(d.y-next.first) + abs(d.x-next.second);
			if(d.next+1 == l)
				ans = min(ans, nextcost);
			else
				Q.push(Data(next.first, next.second, i, d.next+1, nextcost));
		}
	}
	printf("%d\n", ans==INF ? -1 : ans);

	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:44:29: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:47:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:51:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]

Judge Result