範例程式碼 uva1714
//uva1714
#include <iostream>
#include <map>
#include <cstring>
#include <string>
#include <utility>
#include <algorithm>
#include <cmath>
#include <map>
#include <queue>
using namespace std;
char board[64][64]; //keyboard
char query_string[10001]; //input string
int len_q; //len of query_string
int nex[64][64][4][2];
int visitCount[64][64];
int R, C;
const int dx[4] = {0, 0, 1, -1}; //row offset
const int dy[4] = {1, -1, 0, 0}; //col offset
int answer = 0;
//BFS node
class Node {
public:
int x,y; //row,col
int cc_q; //count for input string
int nstep; //number of steps of keyboard
};
//build table of next move positions
//for example: "aaab", [0]'s next move is [3]
//in case of out of range position, record -1
void build_next_table()
{
for(int i=0;i<R;i++) {
for(int j=0;j<C;j++) {
for(int k=0;k<4;k++) //four directions
{
//find next different char in direction k
//note: for the case of out of range, next=-1
int x=i+dx[k];
int y=j+dy[k];
//out of range
if(x<0||x>=R||y<0||y>=C) {
nex[i][j][k][0]=-1;
nex[i][j][k][1]=-1;
continue;
}
int flag_out = 0;
while(board[i][j]==board[x][y]) {
x+=dx[k];
y+=dy[k];
if(x<0||x>=R||y<0||y>=C) {
flag_out = 1;
break;
}
}
if(flag_out) {
nex[i][j][k][0]=-1;
nex[i][j][k][1]=-1;
} else {
nex[i][j][k][0]=x;
nex[i][j][k][1]=y;
}
}
}
}
}
void print_nex() {
for(int i=0;i<R;i++) {
for(int j=0;j<C;j++) {
for(int k=0;k<4;k++) //four directions
{
cout << "R,C[" << i << "," << j << "]=(" << nex[i][j][k][0] << "," << nex[i][j][k][1] << ")" << "board=" << board[i][j] << endl;
}
}
}
}
/*
void print_visitCount() {
for(int i=0;i<R;i++) {
for(int j=0;j<C;j++) {
cout << visitCount[i][j] << "(" << "" << board[i][j] << ") ";
}
cout << endl;
}
cout << endl;
}
*/
void clear_visitCount() {
for(int i=0;i<R;i++) {
for(int j=0;j<C;j++) {
visitCount[i][j] = -1;
}
}
}
void print_queue_node(Node &v) {
cout << v.x << "," << v.y << "(" << board[v.x][v.y] << ")" << v.cc_q << "(" << query_string[v.cc_q] << ")" << v.nstep << endl;
}
int BFS()
{
queue <Node> q;
Node v = Node {0,0,0,0};
q.push(v);//init BFS node, upper left position
//print_queue_node(v);
//print_visitCount();
while(!q.empty())
{
Node u = q.front();
q.pop();
if(board[u.x][u.y]==query_string[u.cc_q])//find the current char in the query string
{
if(u.cc_q==len_q-1)//The search ends if the last char is found.
{
answer = u.nstep + 1;//+1 for performing 'SEL' on 'Enter' key
return answer;
}
u.nstep++;//+1 for performing 'SEL' on the current char
u.cc_q++; //start new point for next char in the query string
visitCount[u.x][u.y]=u.cc_q;//record visitCount count
q.push(u);
//print_queue_node(u);
//print_visitCount();
}
else //normal BFS
{
int x,y;
for(int k=0;k<4;k++) {
x=nex[u.x][u.y][k][0];
y=nex[u.x][u.y][k][1];
if(x<0||x>=R||y<0||y>=C)
continue; //stop search if out of range
if(visitCount[x][y]>=u.cc_q)
continue; //stop search for previous visitCounted position
//generate next level node in direction k
visitCount[x][y]=u.cc_q;
Node w = Node{x,y,u.cc_q,u.nstep+1};
q.push(w);
//print_queue_node(w);
//print_visitCount();
}
}
}
return answer;
}
int main() {
while (scanf("%d %d", &R, &C) != EOF) {
//cout << si << endl;
for (int i = 0; i < R; i++) {
scanf("%s", board[i]);
//cout << board[i] << endl;
}
scanf("%s", query_string);
//cout << query_string << endl;
len_q = strlen(query_string);
query_string[len_q]='*'; //add the last "Enter" key, (='*')
len_q += 1;
//clear visitCount count
clear_visitCount();
build_next_table();
//print_nex();
BFS();
cout<<answer<<endl;
}
return 0;
}