範例程式碼 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;
}